Math 228: Kuratowski’s Theorem - CMU

1 math 228: kuratowski s TheoremMary Radcliffe1 IntroductionIn this set of notes, we seek to prove kuratowski s Theorem : Theorem 1( kuratowski s Theorem ).LetGbe a graph. ThenGis nonplanar if and only ifGcontainsa subgraph that is a subdivision of eitherK3, order to prove this Theorem , let s first walk through some the definitions here, and verify that bothK3,3andK5are , let s considerK3,3. As was seen in the previous set of notes regarding graph embeddings,K3,3can be embedded on the torus. It was asserted in those notes thatK3,3is not planar, but it was notproved. Hence, let us prove that assertion ,3is not us prove by contradiction. Suppose, to the contrary, thatK3,3is planar. Then there is a planeembedding ofK3,3satisfyingv e+f= 2, Euler s formula. Note that here,v= 6 ande= , sinceK3,3is bipartite, it contains no 3-cycles (since it contains no odd cycles at all). So eachface of the embedding must be bounded by at least 4 edges fromK3,3. Moreover, each edge is countedtwice among the boundaries for faces.

2 Hence, we must havef 2e/4 =e/2 = , plugging this data in to Euler s formula, we obtain2 =v e+f 6 9 + = ,which is clearly false. Hence, it cannot be thatK3,3is 1: The two nonplanar graphsK3,3andK5discussed in the introduction,and crucial to kuratowski s we turn toK5. To prove thatK5is nonplanar, we appeal to a Problem 1 from Homework not Problem 1 in Homework 9, we have that a planar graph must satisfye 3v 6. Note thatforK5,e= 10 andv= 5. Since 106 9, it must be thatK5is not Subdivisions and SubgraphsGood, so we have two graphs that are not planar (shown in Figure 1). It is also straightforward to noticethat if we took one of the edges from one of these graphs, and replaced it with a path of length 2 (essentially,stick another vertex in the middle of the edge), then the graph should still be nonplanar (see Figure 2).Indeed, adding this extra vertex in the middle of the edge doesn t change the fundamentalshapeof thestructure, which is what makes it nonplanar to begin 2: The graphK5after subdividing some edges.

3 Notice that the shape ofthe structure is still unchanged, even with extra vertices having been includedalong some edges, and hence the structure is still us formally define this as asubdivision, as follows. A graphHis said to be asubdivisionof a graphGifHcan be obtained fromGby successively deleting an edge inG, and replacing that edge with a length2 path (whose central vertex was not originally part ofG). An edge that has been removed and replacedwith a length 2 path is said to besubdividedinH. Fundamentally, we can just think of taking the edge,and dividing it into two pieces to form two different edges. So the subdivision ofK5shown in Figure 2 isobtained by making 4 subdivisions, one along the bottom edge, one along the edge in the middle of thestar, and two along the rightmost exterior edge. To formalize what we have discussed:Lemma a graph. ThenGis planar if and only if every subdivision ofGis is to say, the act of subdividing a graph does not change the planarity of the graph at all, sincethe fundamental shape (the topological shape) has not note also here that quite trivially, if we have a planar graph, and we take a subgraph, it too mustbe planar.

4 Indeed, we can simply take the original graph, embed it in the plane, and then remove anyedges or vertices not present in the subgraph to produce a plane drawing of the desired subgraph. Thisis, certainly, a very trivial property, but as it plays a fundamental role in kuratowski s Theorem , I feelcompelled to give it an entire a planar graph. Then every subgraph ofGis also are now set up to begin dissecting both the statement and the proof of kuratowski s kuratowski s Theorem : SetupWe begin this section just by restating the Theorem from the beginning of the introduction, to remindourselves what we are doing 1( kuratowski s Theorem ).LetGbe a graph. ThenGis nonplanar if and only ifGcontainsa subgraph that is a subdivision of eitherK3, that one direction here is made trivial by the lemmas presented in the previous section. Indeed,ifGcontains a nonplanar subgraph, then Lemma 2 immediately implies thatGis nonplanar. But bythe discussion in the introduction, we also know thatK3,3andK5are nonplanar, so ifGcontains eitherof these, it should be nonplanar.

5 Allowing for subdivisions allows us to colloquially phrase kuratowski sTheorem as follows: Theorem 1( kuratowski s Theorem , layman s terms).We know two nonplanar graphs, they areK3,3andK5. So of course any graph containing those is not planar. In fact, any graph containing something thathas the same basic shape as those is nonplanar (that s the subdivision thing). And not only that, but everynonplanar graph has one of these two bad shapes inside it as a subgraph. That s really the only way to is the crux of the Theorem : the only way to be nonplanar is to have one of these two known badshapes as a , we begin the proof. Before we begin, let me just remind you of a few definitions that will come a graphGis a vertexvsuch thatG\{v}has more components thanGitself. That is,it s a vertex whose removal disconnects some part of the graph that used to be a graphGis a subgraphBofGsuch thatBhas no cut vertices, but if we add any othervertices toB, it does have cut vertices (that is, it is a maximal subgraph inGhaving no cut vertices).

6 In this way we can view any graphGas being built of blocks, that are simply pasted together at graph is called2-connectedif it is connected and has no cut-vertices. We can think of 2-connectedas if you want to disconnect it, you ll have to take away 2 things. (In this way, we can generalize to k-connected by just replacing the number 2 with the numberkin the above quotated phrase, and it willbe correct.)We have one more (nontrivial) lemma before we can begin the proof of the Theorem in a 2-connected graph, andu, vvertices ofG. Then there exists a cycle inGthatincludes will prove this by induction on the distance , note that the smallest distance is 1, which can be achieved only ifuis adjacent tov. Supposethis is the case. Note thatucannot have degree 1, since otherwise, it must be thatvis a cut vertex (seeFigure 3). Hence,umust have another neighbor inG, us consider the graphG\{u}. Notice that this graph is still connected, by the definition of 2- connectedness , and hence there exists a path inG\{u}betweenwandv.

7 Moreover, this path cannot usethe vertexu, since it has been deleted from the this path on both ends inGcreates a cycle inG, that contains , let us suppose the result is known for anyu, vhaving distance at mostd 1. Letu, v V(G)have distance exactlyd. LetQbe a path of lengthdbetweenuandv. Takewto be the point in the pathQadjacent tov. Note thatd(u, w) =d 1, so there exists a cycleCinGthat contains bothuandw. Ifvis a member of this cycle, then we are done, as we have a cycle that contains 3: Notice that in the case thatuis of degree 1, its neighborvmust bea cut-vertex, since deletingvwould result in at least two components, one ofthem being justuby itself, and the others containing the rest of the not, thenvappears outside the cycle. Moreover, sinceG\{w}is connected, there exists a pathPbetweenuandvthat does not include the vertexw. We note that this path can contain vertices of thecycleC, just not the vertexw. Draw this as shown in Figure 4, and then create a cycle including bothuandvby tracing around the exterior of the 4: The structure ofCandPin the case thatd(u, v) =d.

8 Note that thecycleCis drawn in red, and the pathPis drawn in black. Both these can havemore vertices that are not drawn. The intersections ofPwith the cycleCaredrawn arbitrarily, and can occur in many different ways, this is just an , with all this setup done, we are ready to begin the proof of Kuratowki s kuratowski s Theorem : ProofFor simplicity throughout the proof, we will use lines to indicate not just edges in the graph, but pathsas well. This will keep our drawings from getting too cluttered, and will still show the shapes we areinterested in (since embeddability is all, really, about shapes).Proof of kuratowski s first note that the backward direction is trivial, by immediately ap-plying Lemmas 1 and , let us consider the forward direction. We wish to show that any nonplanar graph contains asubdivision ofK3,3orK5. Let us work by contradiction. Suppose that the Theorem is not true, so thatthere exists a nonplanar graph having neither a subdivision ofK3,3nor a subdivision ofK5as a among all such counterexamples, let us choose the minimal counterexampleG; where here we meanGto be minimal in the sense that any graph on either fewer vertices or edges satisfies the be of Claim from Homework 9, Problem 2 that a graph is planar if and only if every block ofthe graph is planar.

9 Hence, we have that sinceGis nonplanar, it must contain a nonplanar block. If thiswere a proper subgraph, this would be a smaller nonplanar graph that does not contain a subdivision ofK3,3orK5, contradicting the minimality ofG. Hence,Gmust itself be a block, in which caseGmust , so we know our graphGdoes not contain any cut vertices. In addition, we can rule out thepresence of vertices of degree 2 inG, as not contain any vertices of degree of Claim , to the contrary, thatGcontains a vertex of degree 2, sayv. Let the neighborsofvbeuandw. We consider two cases, according to ifuis adjacent towor adjacent tow, consider the graphHobtained fromGby removingv. By minimality ofG, itmust be thatHis planar. Find a plane embedding ofH, and then insert the pathuvwnext to the edgeuwas shown in Figure 5. By inserting this path into the region that hasuwon its boundary, we canensure a plane embedding ofG, which is a 5 For the second case, ifuis not adjacent tow, remove the vertexvand replace it with the edgeuwto obtain a graphH.

10 Note that this graph is smaller thanG, and hence by minimality ofGit must beplanar. Find a plane drawing ofH, and then subdivide the edgeuwto produceGagain. By Lemma 1, itmust be the case thatGis also planar, a in either case we produce a contradiction, we therefore have thatGcannot contain any vertex ofdegree , it must be that our graphGis both 2-connected, and has every vertex with degree 3 or next claim is an exercise in Homework have an edgeuvsuch thatG\{uv}is still of Claim 3 in Homework \{uv}, the subgraph ofGobtained by removing the edge (but not the vertices) note that by the minimality ofG, we must have thatHis planar. Moreover,His 2-connected, sothere must exist at least one cycle inHthat includes both the verticesuandvby Lemma a plane embedding ofHin such a way that there is a cycleCsatisfying the following:5 Ccontains bothuandv The number of regions inside ofCin the embedding is maximal among all other embeddings. IfC is any other cycle that contains bothuandv, the number of regions insideC in a planeembedding ofHis less than (or equal to) the number of regions is to say, we have chosen a cycle containinguandvso that the number of regions inside the cycleis maximized among ALL cycles containinguandv, among ALL embeddings ofH.