Overlapping bridges on graphs

41 Views Asked by At

I have trouble understanding the first part of proof of the Theorem 10.25 of Bondy and Murty's textbook. The Theorem states "Overlapping bridges are either skew or equivalent 3-bridges", where skew bridges are defined as bridges with two couples of distinct vertices that alternate in cyclic order on the cycle where the two bridges are defined. The proof starts by stating that if one of two bridges is a 2-bridge, then the bridges are skew. Why is that? Aren't there supposed to be 4 different vertices?

1

There are 1 best solutions below

0
On

In the definition of skew, the four different vertices are four distinct vertices of C. Two of them (u,v) are contained in B (and hence connected by a path in B), while the other two (u',v') are contained in B' (and hence connected by a path in B'), and their order along the cycle is alternating between B and B'. There can be other paths, and vertices can belong to both B and B', but the point is that already the paths u-v and u'-v' cannot be drawn on the same side of the cycle. Hence skew bridges need to be drawn on opposite sides of the cycle.

If two bridges B and B' overlap, but say B is a 2-bridge, it has two attachments u and v which split C into two segments. Since they don't overlap, B' must have an attachment vertex in the interior of both segments, that is, vertices u' and v' such that their order on the cycle is u u' v v'.

Overall the idea here is to show that there are two kinds of obstructions to drawing bridges on the same side of a cycle: skew bridges (two paths with alternating endpoints on C) and equivalent 3-bridges (kind of a corner case).