10.1 Plane and Planar Graphs245Theorem 10.1 THE JORDAN CURVE THEOREMAny simple closed curve C in the plane partitions the rest of the plane into tudisjoint arcwise-connected open sets.Although this theorem is intuitively obvious, giving a formal proof of it is quitetricky.Thetwo open sets into which ae closed curve Cpartitions theplanor and the erterior of C. We denote them by int(C) and ext(C),arecalled the interand their closures by Int(C) and Ext(C), respectively (thus Int(C) n Ext(C) = C)The Jordan Curve Theorem implies that every arc joining a point of int(C) to apoint of ext(C) meets C in at least one point (see Figure 10.2)teext(C)Fig.10.2.The Jordan Curve TheoremFigurebshowsthat thegraph Keisplanar.ThegraphKs,ontheothehand, is not planar. Let us see how the Jordan Curve Theorem can be used todemonstrate this fact.Theorem 10.2 K, is nonplanar.Proof By contradiction. Let G be a planar embedding of Ks, with verticesA.Us.BecauseGiscomplete.anytwo ofitsverticeare joined by an..edge.Nowthecycle=uaisasimplecosed curveitheplane,andthevertex u4 must lie either in int(C) or in ext(C). Without loss of generality, we maysuppose that u4 E int(C). Then the edges vi4, v2u4, v3v4 all lie entirely in int(C),too (apart from their ends V1, V2, v3) (see Figure 10.3).Consider the cycles Ci = v2v3va2,C2:Vi4U3, and C3=iu2U4ui.Observe that v; e ext(C), i = 1,2,3. Because v,us e E(G) and G is a planegraph, it follows fromthe Jordan Curve Theorem that us E ext(C), i = 1,2,3,too. Thus us E ext(C). But now the edge uaus crosses C, again by the JordanCurve Theorem. This contradicts the planarity of the embedding G.口A similar argument can be used toestablish that K3,s is nonplanar, too (Exercise 10.1.1b).10.1 Plane and Planar Graphs 245 Theorem 10.1 The Jordan Curve Theorem Any simple closed curve C in the plane partitions the rest of the plane into two disjoint arcwise-connected open sets.
Although this theorem is intuitively obvious, giving a formal proof of it is quite tricky. The two open sets into which a simple closed curve C partitions the plane are called the interior and the exterior of C. We denote them by int(C) and ext(C), and their closures by Int(C) and Ext(C), respectively (thus Int(C) ∩ Ext(C) = C). The Jordan Curve Theorem implies that every arc joining a point of int(C) to a point of ext(C) meets C in at least one point (see Figure 10.2). C int(C) ext(C) Fig. 10.2. The Jordan Curve Theorem Figure 10.1b shows that the graph K5 \e is planar. The graph K5, on the other hand, is not planar. Let us see how the Jordan Curve Theorem can be used to demonstrate this fact. Theorem 10.2 K5 is nonplanar. Proof By contradiction. Let G be a planar embedding of K5, with vertices v1,v2,v3,v4,v5. Because G is complete, any two of its vertices are joined by an edge. Now the cycle C := v1v2v3v1 is a simple closed curve in the plane, and the vertex v4 must lie either in int(C) or in ext(C). Without loss of generality, we may suppose that v4 ∈ int(C). Then the edges v1v4,v2v4,v3v4 all lie entirely in int(C), too (apart from their ends v1,v2,v3) (see Figure 10.3). Consider the cycles C1 := v2v3v4v2, C2 := v3v1v4v3, and C3 := v1v2v4v1. Observe that vi ∈ ext(Ci), i = 1, 2, 3. Because viv5 ∈ E(G) and G is a plane graph, it follows from the Jordan Curve Theorem that v5 ∈ ext(Ci), i = 1, 2, 3, too. Thus v5 ∈ ext(C). But now the edge v4v5 crosses C, again by the Jordan Curve Theorem. This contradicts the planarity of the embedding G.
A similar argument can be used to establish that K3,3 is nonplanar, too (Ex￾ercise 10.1.1b)