10.4 Bridges265bridge contained in Int(C) is called an inner bridge, a bridge contained in Ext(C)an outer bridge. In Figure 10.16, Bi and B, are inner bridges, and Bg and By areouter bridges.Theorem 10.26 Inner (outer) bridges avoid one another.Proof Let B and B' be inner bridges of a cycle C in a plane graph G. Supposethattheyoverlap.ByTheorem10.25,theyareeitherskeworequivalent3-bridges.In both cases, we obtain contradictionsCase I: B and B' are skew. By definition, there exist distinct vertices u,u in B andu', u' in B', appearing in the cyclic order u, u,v, u' on C. Let uPu be a path in Band u'P'u'a path in B',both intermally disjoint from C.Consider the subgraphH := CU PU P' of G (see Figure 10.17a). Because G is plane, so is H. Let Kbe the plane graph obtained from H by adding a vertex in ext(C) and joiningit to u,u',v,u' (see Figure 10.17b). Then K is a subdivision of Ks. But this isimpossible.Ksbeingnonplanar(b)(a)Fig.10.17.Proof of Theorem 10.26, Case 1: (a) the subgraph H, (b) the subdivision KofKsCase 2: B and B' are equivalent 3-bridges, Denote by S := [ui, u2, u3] theirmon set of vertices of attachment. By Exercise 9.2.3, there exists a (u, S)-fanFin B, for some internal vertex ofB; likewise, thereexists a (u,)-fan F'inB', for some internal vertex u' of B'. Consider the subgraph H := F U F" of G.Because G is plane, so is H.Let K be the plane graph obtained from H byaddinga vertexin ext(C)and joining it to thethreevertices of S.Then K is a subdivisionof K3.3. But this is impossible, because K3.3 is nonplanar (see Figure 10.18)We conclude that inner bridges avoid one another. Similarly, outer bridgavoid one anotherIt is convenient to visualize the above theorem in terms of the bridge-overlapgraph. Let G be a graph and let C be a cycle of G. The bridge-overlap graph of Cis the graph whose vertex set is the set of all bridges of C in G, two bridges being10.4 Bridges 265 bridge contained in Int(C) is called an inner bridge, a bridge contained in Ext(C) an outer bridge. In Figure 10.16, B1 and B2 are inner bridges, and B3 and B4 are outer bridges. Theorem 10.26 Inner (outer) bridges avoid one another. Proof Let B and B be inner bridges of a cycle C in a plane graph G. Suppose that they overlap. By Theorem 10.25, they are either skew or equivalent 3-bridges. In both cases, we obtain contradictions. Case 1: B and B are skew. By definition, there exist distinct vertices u,v in B and u ,v in B , appearing in the cyclic order u,u ,v,v on C. Let uPv be a path in B and u P v a path in B , both internally disjoint from C. Consider the subgraph H := C ∪ P ∪ P of G (see Figure 10.17a). Because G is plane, so is H. Let K be the plane graph obtained from H by adding a vertex in ext(C) and joining it to u,u ,v,v (see Figure 10.17b). Then K is a subdivision of K5. But this is impossible, K5 being nonplanar. P P
u v u
v
(a) (b) Fig. 10.17. Proof of Theorem 10.26, Case 1: (a) the subgraph H, (b) the subdivision K of K5 Case 2: B and B are equivalent 3-bridges. Denote by S := {v1,v2,v3} their common set of vertices of attachment. By Exercise 9.2.3, there exists a (v,S)-fan F in B, for some internal vertex v of B; likewise, there exists a (v ,S)-fan F in B , for some internal vertex v of B . Consider the subgraph H := F ∪ F of G. Because G is plane, so is H. Let K be the plane graph obtained from H by adding a vertex in ext(C) and joining it to the three vertices of S. Then K is a subdivision of K3,3. But this is impossible, because K3,3 is nonplanar (see Figure 10.18). We conclude that inner bridges avoid one another. Similarly, outer bridges avoid one another.
It is convenient to visualize the above theorem in terms of the bridge-overlap graph. Let G be a graph and let C be a cycle of G. The bridge-overlap graph of C is the graph whose vertex set is the set of all bridges of C in G, two bridges being