27010 Planar GraphsLemma 10.33 Let G be a graph with a 2-verter cut [z,y]. Then each markedfr,yl-component ofG is isomorphicto aminor ofGProof Let H be an (r,y]-component of G, with marker edge e, and let rPy bea path in another (r,y)-component of G. Then HU P is a subgraph of G. ButHu P is isomorphic to a subdivision of G + e, so G + e is isomorphic to a minorof G.口Lemma 10.34 Let G be a graph with a 2-verter cut [z,y]. Then G is planar ifand only if each of its marked (z,y]-components is planar.Proof Suppfirstthat G is.planar.ByLemula10.33.eacmarked fr.y!componentofGisisomorphictoaminorofG,henceisplanarbyProposition1o.31Conversely, suppose that G has k marked (r,y)-components each of which isplanar. Let e denote their common marker edge. Applying Exercise 10.4.1 andinduction on k, it follows that G + e is planar, hence so is GIn view of Lemmas 10.33 and 10.34, it suffices to prove Wagner's Theorem for 3connected graphs.It remainss,therefore,to showthat every3-conmectednonplanagraph has either a Ks-minor or a K3,3-minor. We present an elegant proof of thisstatement.It is due to Thomassen (1981),and is based on his Theorem 9.10Theorem 10.35 Every 3-connected nonplanar graph has a Kuratowski minorProof Let G be a 3-connected nonplanar graph. We may assume that G is simpleBecauourorfeweotcesareplanar,wehaven>5.Weproceedgraphby induction on n. By Theorem 9.10, G contains an edge e = ry such that H :-G /e is 3-connected. If H is nonplanar, it has a Kuratowski minor, by inductionSince every minor of H is also a minor of G, we deduce that G too has a Kuratowskiminor. So we may assume that H is planar.Consider aplaneembedding H of H.Denotebyz thevertex of Hformedby contracting e. Because H is loopless and 3-connected, by Corollary 10.8 theneighboursofzlieoa cycle C.theboundary of someface f of H-z.DenotebyB, and By, respectively, the bridges of C in Gle that contain the vertices andse, first, that B and By avoid each other. In this case, Ba and By canu1be embedded in the face f of H - z in such a way that the vertices r and y belongto the same face of the resulting plane graph (H - z)uB,U By (see Figure 10.20).The edge ry can now be drawn in that face so as to obtain a planar embedding ofG itself, contradicting the hypothesis that G is nonplanalItfollows that Band B do not avoid each other.that is.they overlap.ByTheorem 10.25, they are therefore either skew or else equivalent 3-bridges. Intheforcase, G has a K3.3-minor; in the latter case, G has a Ks-minor (seeFigure 10.21).广We note that the same proof serves to show that every simple 3-connectedplanar graph admits a conver embedding, that is, a planar embedding all of whose270 10 Planar Graphs Lemma 10.33 Let G be a graph with a 2-vertex cut {x,y}. Then each marked {x,y}-component of G is isomorphic to a minor of G.
Proof Let H be an {x,y}-component of G, with marker edge e, and let xPy be a path in another {x,y}-component of G. Then H ∪ P is a subgraph of G. But H ∪ P is isomorphic to a subdivision of G + e, so G + e is isomorphic to a minor of G.
Lemma 10.34 Let G be a graph with a 2-vertex cut {x,y}. Then G is planar if and only if each of its marked {x,y}-components is planar. Proof Suppose, first, that G is planar. By Lemma 10.33, each marked {x,y}- component of G is isomorphic to a minor of G, hence is planar by Proposition 10.31. Conversely, suppose that G has k marked {x,y}-components each of which is planar. Let e denote their common marker edge. Applying Exercise 10.4.1 and induction on k, it follows that G + e is planar, hence so is G.
In view of Lemmas 10.33 and 10.34, it suffices to prove Wagner’s Theorem for 3- connected graphs. It remains, therefore, to show that every 3-connected nonplanar graph has either a K5-minor or a K3,3-minor. We present an elegant proof of this statement. It is due to Thomassen (1981), and is based on his Theorem 9.10. Theorem 10.35 Every 3-connected nonplanar graph has a Kuratowski minor. Proof Let G be a 3-connected nonplanar graph. We may assume that G is simple. Because all graphs on four or fewer vertices are planar, we have n ≥ 5. We proceed by induction on n. By Theorem 9.10, G contains an edge e = xy such that H := G/e is 3-connected. If H is nonplanar, it has a Kuratowski minor, by induction. Since every minor of H is also a minor of G, we deduce that G too has a Kuratowski minor. So we may assume that H is planar. Consider a plane embedding H of H. Denote by z the vertex of H formed by contracting e. Because H is loopless and 3-connected, by Corollary 10.8 the neighbours of z lie on a cycle C, the boundary of some face f of H − z. Denote by Bx and By, respectively, the bridges of C in G \ e that contain the vertices x and y. Suppose, first, that Bx and By avoid each other. In this case, Bx and By can be embedded in the face f of H −z in such a way that the vertices x and y belong to the same face of the resulting plane graph (H −z)∪Bx ∪By (see Figure 10.20). The edge xy can now be drawn in that face so as to obtain a planar embedding of G itself, contradicting the hypothesis that G is nonplanar. It follows that Bx and By do not avoid each other, that is, they overlap. By Theorem 10.25, they are therefore either skew or else equivalent 3-bridges. In the former case, G has a K3,3-minor; in the latter case, G has a K5-minor (see Figure 10.21).
We note that the same proof serves to show that every simple 3-connected planar graph admits a convex embedding, that is, a planar embedding all of whose