26910.5Fig. 10.19. Contracting the Petersen graph to KsIf F is a minoiorofG.wewriteF<G.ByanF-minorofG.whereFisalarbitrary graph, we mean anorofG whichis isomorphic to F.It is importanttopoint out that any graph whichcontains an F-subdivision alsohas an F-minor:to obtain F as a minor, one simply deletes the vertices and edges not im thesubdivision, and then contracts each subdivided edge to a single edge.For examplebecause the Petersen graph contains a K3.3-subdivision (Exercise 10.1.3), it alsohas a K3.3-minor, Conversely, provided that F is a graph of maximum degreethree or less, any graph which has an F-minor also contains an F-subdivision(Exercise 10.5.3a)WAGNER'S THEOREMAs observed in Section i0.2, the deletion or contraction of an edge in a planargraph results again in a planar graph. Thus we haves口Proposition 10.31 Minors of planar graphs are planarA minor which is isomorphic to K, or K3.3 is called a Kuratouski minor. Because Ks and K3,3 are nonplanar, Proposition 10.31 implies that any graph whichhas a Kuratowski minor is nonplanar. Wagner (1937) proved that the converse istrueWAGNER'STHEOREMTheorem 10.32A graph is planar if and only if it has no Kuratowski minoWererked above thataph which coF-subdivisionalsnhtF-minor.Thus Kuratowski's Theorem implies Wagner's Theorem.On the otherhand, because K3.3 has maximum degree three, any graph which has a K-contains a K3,3-subdivision (Exercise 10.5.3a).Furthermore, any graph which hasa Kg-minor necessarily contains a Kuratowski subdivision (Exercise 10.5.3b). ThusWagner's Theorem implies Kuratowski's Theorem, and the two are therefore equiv-alentIt turns out to be slightly more convenient to prove Wagner's variant of Kura-towski's Theorem. Before doing so, we need to establish two simple lemmas10.5 Kuratowski’s Theorem 269 Fig. 10.19. Contracting the Petersen graph to K5 If F is a minor of G, we write F  G. By an F-minor of G, where F is an arbitrary graph, we mean a minor of G which is isomorphic to F. It is important to point out that any graph which contains an F-subdivision also has an F-minor: to obtain F as a minor, one simply deletes the vertices and edges not in the subdivision, and then contracts each subdivided edge to a single edge. For example, because the Petersen graph contains a K3,3-subdivision (Exercise 10.1.3), it also has a K3,3-minor. Conversely, provided that F is a graph of maximum degree three or less, any graph which has an F-minor also contains an F-subdivision (Exercise 10.5.3a). Wagner’s Theorem As observed in Section 10.2, the deletion or contraction of an edge in a planar graph results again in a planar graph. Thus we have: Proposition 10.31 Minors of planar graphs are planar.
A minor which is isomorphic to K5 or K3,3 is called a Kuratowski minor. Be￾cause K5 and K3,3 are nonplanar, Proposition 10.31 implies that any graph which has a Kuratowski minor is nonplanar. Wagner (1937) proved that the converse is true. Theorem 10.32 Wagner’s Theorem A graph is planar if and only if it has no Kuratowski minor. We remarked above that a graph which contains an F-subdivision also has an F-minor. Thus Kuratowski’s Theorem implies Wagner’s Theorem. On the other hand, because K3,3 has maximum degree three, any graph which has a K3,3-minor contains a K3,3-subdivision (Exercise 10.5.3a). Furthermore, any graph which has a K5-minor necessarily contains a Kuratowski subdivision (Exercise 10.5.3b). Thus Wagner’s Theorem implies Kuratowski’s Theorem, and the two are therefore equiv￾alent. It turns out to be slightly more convenient to prove Wagner’s variant of Kura￾towski’s Theorem. Before doing so, we need to establish two simple lemmas