24610 Planar Graphst(C2nt(C3)nt(C)ext(C)Fig. 10.3. Proof of the nonplanarity of KsSUBDIVISIONSAny graph derived from a graph G by a sequence of edge subdivisions is calleda subdivision of G or a G-subdivision. Subdivisions of Kg and K3.3 are shown inFigure 10.4.XX(a)(b)Fig. 10.4. (a) A subdivision of Ks, (b) a subdivision of K3.3The proof of the following proposition is straightforward (Exercise 10.1.2)Proposition 10.3 A graph G is planar if and only if every subdivision of G isplanar.口BecauseKsandK3.3arenonplanar,Proposition10.3impliesthatnoplanargraph can contain a subdivision of either Ks or K3.3.A fundamental theorem dueto Kuratowski (1930) states that, conversely, every nonplanar graph necessarilycontains a copy of a subdivision of one of these two graphs. A proof of Kuratowski'sTheorem is given in Section 10.5.As mentioned in Chapter 1 and illustrated in Chapter 3, one may considerembeddings of graphs on surfaces other than the plane. We show in Section 10.6246 10 Planar Graphs v1 v2 v3 v4 C int(C1) ext(C) int(C2) int(C3) Fig. 10.3. Proof of the nonplanarity of K5 Subdivisions Any graph derived from a graph G by a sequence of edge subdivisions is called a subdivision of G or a G-subdivision. Subdivisions of K5 and K3,3 are shown in Figure 10.4. (a) (b) Fig. 10.4. (a) A subdivision of K5, (b) a subdivision of K3,3 The proof of the following proposition is straightforward (Exercise 10.1.2). Proposition 10.3 A graph G is planar if and only if every subdivision of G is planar.
Because K5 and K3,3 are nonplanar, Proposition 10.3 implies that no planar graph can contain a subdivision of either K5 or K3,3. A fundamental theorem due to Kuratowski (1930) states that, conversely, every nonplanar graph necessarily contains a copy of a subdivision of one of these two graphs. A proof of Kuratowski’s Theorem is given in Section 10.5. As mentioned in Chapter 1 and illustrated in Chapter 3, one may consider embeddings of graphs on surfaces other than the plane. We show in Section 10.6