Skip to main content

Section 4.3 Kuratowski's Theorem

The planrity Algorithm for Hamiltonian graphs gives a very convenient and systematic way to determine whether a Hamiltonian graph is planar or not, and we saw that with some work it can be hacked to work for graphs that are "almost" Hamiltonian -- that have a cycle that go through all but one or two vertices, say.

Stretching these ideas further, the general logic of considering cycles and applying the Jordan Curve theorem to them would provide a way to prove whether an abritrary graph is planar or not, but as we have more or more vertices that aren't on our cycle to consider the arguments would get more and more complicated, and it's clear that a better method is desirable. In this section we will present, (but not completely prove) Kuratowski's theorem, which gives a method to determine whether or not an arbitrary graph is planar.

Subsection 4.3.1 Planarity, subgraphs, and subdivisions

The idea behind Kuratowski's theorem rests on two small observations, which we illustrate in a simple example before discussing more formally.

Figure 4.3.1. Two nonplanar graphs

The graphs \(\bfG_1\) and \(\bfG_2\) in Figure 4.3.1 both look a lot like \(K_{3,3}\text{,}\) and since \(K_{3,3}\) is nonplanar, we might expect them to be nonplanar as well, but we need to be careful and precise in checking this. We work this out in the next example.

The graph \(\bfG_1\) in Figure 4.3.1 is \(K_{3,3}\) with a vertex and two edges added to it; put another way, \(K_{3,3}\) is a subgraph of \(\bfG_1\text{.}\) If we could draw \(\bfG_1\) in the plane, we could just ignore this extra vertex and these two edges, and we'd have a drawing of \(K_{3,3}\) in the plane, but we know \(K_{3,3}\) isn't planar. So to avoid contradictions we are forced to conclude that \(\bfG_1\) isn't planar.

The graph \(\bfG_2\) looks just like \(K_{3,3}\text{,}\) but we have added an extra vertex of degree two in the middle of one of the edges. Note that \(K_{3,3}\) is not a subgraph of \(\bfG_2\text{,}\) and so we need to use slightly different reasoning than we did for showing \(\bfG\) isn't planar. But drawing \(\bfG_2\) is just like drawing \(K_{3,3}\) and then adding an extra dot for the new vertex of degree two. If we could draw \(\bfG_2\) in the plane, we could just skip adding this extra dot, and we'd have a drawing of \(K_{3,3}\) in the plane. Again, since we know \(K_{3,3}\) isn't planar, we see that \(\bfG_2\) isn't planar, either.

We will now generalize the methods we used to show \(\bfG\) and \(\bfH\) are nonplanar and summarize them as lemmas. The reasoning we used to prove that \(\bfG\) was nonplanar doesn't need to be changed at all to prove:

We've essentially already proved it, but we'll restate the reasoning in a different way for completeness.

When we draw a graph \(\bfG\) in the plane, we also draw all the subgraphs of \(\bfG\) in the plane. Thus, if \(\bfG\) is planar, then all of its subgraphs are planar. Our lemma is the contrapositive of this statement.

Lemma 4.3.3 is logically equivalent to the discussion above, but it's worth restating the logic in this direction as well: if we can't draw \(\bfG\) in the plane, then we certainly can't draw \(\bfH\) in the plane without edges crossing, as if we could then we'd have a drawing of \(\bfH\) as part of our big drawing.

If \(n\gt 5\text{,}\) then \(K_n\) is not planar by Lemma 4.3.3, because \(K_5\) is a subgraph of \(K_n\text{,}\) and we know that \(K_5\) isn't planar.

We could also have used the fact that \(K_{3,3}\) is a subgraph of \(K_n\text{,}\) and \(K_{3,3}\) is also nonplanar.

To generalize the method we used to prove \(\bfG_2\) is non-planar, we first make a form definition that encapsulates the idea of "adding dots" to the middle of edges:

Definition 4.3.5. Subdivision.

We say that \(\bfG\) is a subdivision of \(\bfH\) if \(\bfG\) is obtained from \(\bfH\) by adding some vertices of degree two in the middle of some of the edges of \(\bfH\text{.}\)

Any path graph \(P_n, n\geq 2\) is a subdivision of the graph \(P_2\) consisting of two vertices with an edge between them. Any cycle graph \(C_m, m\geq 3\) is a subdivision of the triangle \(C_3\)

Suppose that \(\bfG\) was planar, and draw it in the graph. Then erase the, vertices of degree we added when we subdivided \(\bfH\text{,}\) merging the edges on either side to one. We obtain a planar drawing of \(\bfH\text{,}\) a contradiction, and so \(\bfG\) must not have been planar.

Subsection 4.3.2 Kuratowski's Theorem

The definitions and lemma of the previous section essentially prove the "easy" direction of the following theorem, which will be our main tool for proving graphs aren't planar.

We will only prove one direction: that if \(\bfG\) has such a subgraph, then \(\bfG\) is nonplanar; the other direction is more difficult.

Suppose that \(\bfH\) is a subgraph of \(\bfG\) that is subdivision of \(K_{3,3}\) or \(K_5\text{.}\) Since we've proven \(K_{3,3}\) and \(K_5\) are nonplanar, we know \(\bfH\) is nonplanar by Lemma 4.3.7. Now since we \(\bfH\) is a subgraph of \(\bfG\) and we know \(\bfH\) is nonplanar, we know \(\bfG\) is nonplanar by Lemma 4.3.3.

Although we've only proven one direction of Kuratowski's theorem, it's the important direction -- the one that lets us prove graphs are nonplanar. The other direction would tell us information about subgraphs of a graph that we already knew was nonplanar for some other reason. Or, taking the contrapositive, it would let us prove a graph was planar by looking at all subgraphs of it and showing none of them looked like \(K_5\) or \(K_{3,3}\text{.}\) But this would be a lot of work and there's a much easier way to show a graph is planar: draw it in the plane! If you're asked to prove a graph is planar, you will almost always also be asked to draw it in the plane.

However, we will implicitly use the hard direction in the following way: if a graph \(\bfG\) is nonplanar, you can always use Kuratowski's theorem to prove that it's nonplanar. This is reassuring because it means our tool will always work to prove it's nonplanar, and that you aren't wasting your time looking for subgraphs that don't exist.

Subsection 4.3.3 Applying Kuratowski's Theorem

The tricky part of using Kuratowski's theorem is actually finding the desired subgraph. We won't really discuss algorithm aspects of this; for any graph you are asked to prove non-planar, it will be possible to do so by educated trial an error. A few rules of thumb may be helpful, however. First, note that subdivision cannot increase the degree of any vertex. So, for \(\bfG\) to have a subgraph that's a subdivision of \(K_5, \bfG\) has to have at least 5 vertice with degree at least 4; if it doesn't, but we still suspect \(\bfG\) to be nonplanar, we know instead that we should be looking for a subdivision of \(K_{3,3}\text{.}\)

Conceptually, it can be useful to think that some vertices of \(\bfG\) are going to be vertices of your \(K_5\) or \(K_{3,3}\text{,}\) and we're going to need to connect those. We can use the remaining vertices of \(\bfG\) as parts of subdivided edges between these, but these extra vertices can only be used in at most one such connection. Thus, these extra vertices are a limited resource we have, and a useful heuristic in looking for subgraph is to take a "greedy" approach, where we choose our vertices to require as few subdivisions as possible to make connections. We illustrate this idea in the next example.

Figure 4.3.10. The Petersen graph, labeled

Let us use Kuratowski's Theorem to prove that the Petersen graph isn't planar; Figure 4.3.10 has a drawing of the Petersen graph with the vertices labeled for referece. Since the Petersen graph is regular of degree three, we know that it can't have a subgrpah that's a subdivision of \(K_5\text{,}\) as it would need to have some vertices of degree 4 or larger.

It makes sense to attempt a greedy algorithm -- in the standard drawing of the Petersen grpah, pick the very top vertex 1 to be "red" and the three vertices adjacent to it to, 2, 5, and 6, to be "blue". We need two more red vertices. All vertices left are adjacent to exactly one blue vertex, so from a greedy point of view there is no preference for which vertex we pick to be the next blue vertex. Let us pick 9 to be another red vertex. Then it is connected directly to blue vertex 6, but we must find paths from 9 to 2 and 5. We could, for instance, take the path 9-4-3-2 to connect to 2, but that would use two vertices up while the path 9-7-2 only uses one extra vertex, and so seems better. Then we can connected 9 to 5 through vertex 4, and vertex 9 has been connected to all the blue vertices.

Now, we need to choose one more vertex to be a red vertex, and the vertices we haven't used are 3, 10, and 8. If we tried to make 3 the last red vertex we run into a problem: we need to connect vertex 3 to 3 other vertices, but one of the edges goes to vertex 4 which was one of the subdivided vertices that we can't visit again. Hence, we only have two possible paths out of 3, and will ever only be able to connect it to two blue vertices. A similar problem occurs if we try to make 10 the last red vertex -- it's adjacent to the vertex 7 used as a subdivided vertex. The remaining choice is vertex 8, which works, as shown in the following diagram.

Figure 4.3.11. A subdivided \(K_{3,3}\) in the Petersen graph

The red and blue vertices of the subdivided \(K_{3,3}\) are shown as squares/circles, and the edges of the subdivided \(K_{3,3}\) are colored thick -- only the dotted edges 7-10 and 3-4 of the Petersen graph are not used in the subgraph.