Graph Theory 101: Why all Non-Planar Graphs Contain K₅ or K₃,₃

An intuitive explanation of Kuratowski’s Theorem and Wagner’s Theorem, with lots of diagrams!

A planar graph is one that can be drawn in a plane without any edges crossing. For example, the complete graph K₄ is planar, as shown by the “planar embedding” below.

One application of planar graphs would be designing a rail network without any intersections. Another common one is designing an electrical circuit or computer chip without any crossing wires.

Two non-planar graphs are the complete graph K5 and the complete bipartite graph K3,3:

• K5 is a graph with 5 vertices, with one edge between every pair of vertices.
• K3,3 is a graph with 6 vertices in two sets of 3, with one edge between each pair of vertices from opposite sets.

No matter how you draw K5 and K3,3, it is not possible to do so without two edges crossing. This can be proved by showing they have too many edges to satisfy Euler’s theorem for non-planar graphs: vertices + faces = edges + 2.

Of course, there are an infinite number of non-planar graphs. But the surprising fact behind Kuratowski’s Theorem and Wagner’s Theorem is that all non-planar graphs “contain” K5 or K3,3! 😲

Now, I need to be a little clearer about the meaning of the word “contain” in this statement. So let’s clarify it by stating the theorems.

Kuratowski’s Theorem

A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 or K3,3.

A “subgraph” is just a subset of vertices and edges. Subgraphs can be obtained by deleting vertices and edges.

A “subdivision” is obtained by subdividing edges, i.e. removing an edge and replacing it with 2-edge path via an intermediate vertex.

For example, it’s not too hard to see K5 hiding in the graph below.

The bottom edge of K5 has been subdivided, then 2 new vertices and 3 new edges have been added up the top.

But let’s look at an example where the subdivision is not so obvious.

The animation below shows how the graph above can be obtained from K5, by subdividing 4 edges, then adding 1 new vertex and 2 new edges.

In a similar way, you can prove a graph is non-planar by showing that it can be obtained from K5 or K3,3 by subdividing edges and adding new vertices and edges.

But as you can imagine, this might not be an easy thing to do.

Wagner’s Theorem allows us to go in the opposite direction (which tends to be easier), by “contracting” the original graph to obtain K5 or K3,3.

Wagner’s Theorem

A finite graph is planar if and only if its minors do not include K5 or K3,3.

A “minor” is a graph that can be obtained by deleting edges or “contracting” edges, i.e. removing an edge and merging its two vertex endpoint into one.

The animation below shows an example of finding a K3,3 minor, by contracting 2 edges and deleting another edge.

The two example graphs shown in the animations above were both non-planar graphs. By showing that they contained K5 or K3,3, we proved they were non-planar.

The fact that all graphs containing K5 or K3,3, either as a subdivision or a minor, must be non-planar, is reasonably intuitive.

But the Kuratowski and Wagner theorems are both “if and only if” theorems, and it’s the other direction that is more impressive… that ALL non-planar graphs contain either K5 or K3,3.

The rest of this article presents an intuitive explanation of why this should be true.

Why all Non-Planar Graphs Contain K5 or K3,3

This argument uses edge contractions and deletions, which is the language of Wagner’s Theorem. But actually the two theorems are logically equivalent anyway.

Starting with any non-planar graph, perform as many edge contractions and deletions as possible without the resulting minor becoming planar. The idea will be to show that this resulting minor must be either K5 or K3,3.

Now remove one edge e, say between vertices v1 and v2, draw a planar embedding, then put the edge e back so that only e crosses other edges.

Furthermore, you can draw the planar embedding so that v2 is on the exterior boundary but v1 is not, as shown above.

This is always possible, because

• v2 must be part of a face boundary that does not contain v1, or there would be nothing for the “crossing edge” e to cross
• Any face in a planar graph can be drawn as the exterior face. This can be proved using stereographic projections. An example is shown below. The face bounded in orange would become the exterior face if we took a projection from the bottom of the sphere instead of the top.

Now, back to our “minimal non-planar minor”. The exterior boundary needs at least two more vertices (or the graph would not be simple). Let these be v3 and v4.

There also needs to be an interior path separating the interior region into two faces, again because the crossing edge e needs something to cross. We also need another vertex v5 to prevent v3 and v4 being connected by two edges (v5 could be on an interior path as shown above, or it could be on the exterior boundary).

So far we have shown that the minimal non-planar minor must have at least 5 vertices. Now we need to show that it must in fact be either K5 or K3,3.

The last step is to consider how v1 could be connected to the rest of the graph. Remember that without edge e we have a planar embedding, but with edge e the graph must be non-planar.

v1 must be connected to at least 2 vertices besides v2, in order to keep the graph non-planar. If v1 is only connected to 2 other vertices, it turns out that one of these must be on the interior path and one must be on the exterior boundary. This gives a K3,3 minor.

If v1 is connected to 3 other vertices besides v2, most of the options can be reduced by edge contractions to one we have already seen above. The only irreducible one is where v1 is connected to v3, v4 and v5. Then you couldn’t contract any edges, as we already showed above that there must be at least 4 vertices. This new option gives a K5 minor, if v5 is also connected by an edge to v2.

If v1 is connected to more than 3 other vertices, there is nothing to stop you contracting edges and reducing the minor to one we have seen already.

And that’s it!

Any non-planar graph can be reduced by edge contractions or deletions to obtain K5 or K3,3. 😎

I hope you found this article interesting and/or useful. If this “intuitive explanation” was not rigorous enough for you, you might prefer the proof in this paper by Tamar-Mattis.

Have a nice day! ☀️ ❄️ 🌈