Kuratowski’s Theorem

Theorem

The following conditions on a graph $\Gamma$ are equivalent:

(a) $\Gamma$ is planar;

(b) $\Gamma$ contains no subdivision of either the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$.

Proof

Let $\Gamma$ be a graph with $V$ vertices, $E$ edges and $F$ faces.

The proof proceeds in two parts: (a)$\implies$(b) and (b)$\implies$(a).

(a) implies (b)

First we consider $K_5$.

$K_5$ has 5 vertices and 10 edges, so by the Euler Polyhedron Formula, a planar embedding would have 7 faces.

But each face has at least 3 edges, while each edge bounds at most two faces.

If we count the incident edge-face pairs, the number of faces is at most (Edges)* 2/3 = 6 + 2/3, a contradiction. Hence $K_5$ is non-planar.

Now consider $K_{3,3}$.

This graph has 6 vertices and 9 edges, and hence 5 faces if it is planar.

Since this graph is bi-partite, from Bipartite Graph has No Odd Cycles, each cycle in $K_{3,3}$ has an even number of edges.

Hence any face must have at least 4 edges, and so the number of faces is at most (Edges)*2/4 = 4.5, a contradiction.

Hence $K_{3,3}$ is non-planar.

Now consider a subdivision of either graph.

The arguments as above continue to work as before, since both $V$ and $E$ have increased by one in the Euler formula, and so the expected value of $F$ is unchanged.

Hence if a graph $\Gamma$ contains a subdivision of $K_5$ or $K_{3,3}$, then $\Gamma$ is not planar, and taking the contrapositive, we have:

$\Gamma$ is a planar graph $\implies \Gamma$ does not contain a subdivision of $K_5$ or $K_{3,3}$.

Source of Name

This entry was named for Kazimierz Kuratowski.