10.4 Bridges267bridge and at least one outer bridge. Because G is simple and connected, thesebridgeis either they are both nontrivial or at least one of themos.is a chord. It follows that C is not a nonseparating cycle.Now suppose that C is a facial cycle of G. By Proposition 10.5, we may assurthat C bounds the outer face of G, so all its bridges are inner bridges. By Theorem 10.26, these bridges avoid one another. If C had a chord ry, the set (r,ywonld be a vertex cut separating the internal vertices of the two ry-segments of C.Likewise, if C had two nontrivial bridges, the vertices of attachment of one of thesebridges would all lie on a single y-segment of the other bridge, and (z,y) wouldbe a vertex cut of G separating the internal vertices of the two bridges. In eithercase, the 3-connectedness of G would be contradicted. Thus C is nonseparating.口A direct conseence of Theorem 10.27 is the following fundamental theorem,duetoWhitney(1933)Theorem 10.28 Every simple 3-connected planar graph has a unique planar embedding.ProofLet Gbea simple3-connected planar graph.By Theorem 10.27,thefacialcycles in any planar embedding of G are precisely its nonseparating cycles. Becausethelater aredefined solely iterms oftheabstract structureofthegraph,theyare the same for every planar embedding of G.口The following corollary is immediateCorollary 10.29 Every simple 3-connected planar graph has a unique dual graph口Exercises+10.4.1 Let Gh and G2 be planar graphs whoserphic to K2ShowthatGUG2isplanar10.4.2 Let H be a subgraph of a graph G. Consider the binary relation ~ onE(G) /E(H), where ei ~ e2 if there exists a walk W in G such that:D the first and the last edges of W are e1 and e2, respectively,Wis internallydisjoint from H (that is,nointernal vertexofWisavertexofH).Show that:a) the relation ~ is an equivalence relation on E(G) / E(H)b) the subgraphs of G/E(H) induced by the equivalence classes under this equivalence relation are the bridges of H in G.10.4 Bridges 267 bridge and at least one outer bridge. Because G is simple and connected, these bridges are not loops. Thus either they are both nontrivial or at least one of them is a chord. It follows that C is not a nonseparating cycle. Now suppose that C is a facial cycle of G. By Proposition 10.5, we may assume that C bounds the outer face of G, so all its bridges are inner bridges. By The￾orem 10.26, these bridges avoid one another. If C had a chord xy, the set {x,y} would be a vertex cut separating the internal vertices of the two xy-segments of C. Likewise, if C had two nontrivial bridges, the vertices of attachment of one of these bridges would all lie on a single xy-segment of the other bridge, and {x,y} would be a vertex cut of G separating the internal vertices of the two bridges. In either case, the 3-connectedness of G would be contradicted. Thus C is nonseparating.
A direct consequence of Theorem 10.27 is the following fundamental theorem, due to Whitney (1933). Theorem 10.28 Every simple 3-connected planar graph has a unique planar em￾bedding. Proof Let G be a simple 3-connected planar graph. By Theorem 10.27, the facial cycles in any planar embedding of G are precisely its nonseparating cycles. Because the latter are defined solely in terms of the abstract structure of the graph, they are the same for every planar embedding of G.
The following corollary is immediate. Corollary 10.29 Every simple 3-connected planar graph has a unique dual graph.
Exercises 10.4.1 Let G1 and G2 be planar graphs whose intersection is isomorphic to K2. Show that G1 ∪ G2 is planar. 10.4.2 Let H be a subgraph of a graph G. Consider the binary relation ∼ on E(G) \ E(H), where e1 ∼ e2 if there exists a walk W in G such that:  the first and the last edges of W are e1 and e2, respectively,  W is internally disjoint from H (that is, no internal vertex of W is a vertex of H). Show that: a) the relation ∼ is an equivalence relation on E(G) \ E(H), b) the subgraphs of G\E(H) induced by the equivalence classes under this equiv￾alence relation are the bridges of H in G. ————— —————