Kuratowski's Theorem

Theorem

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

$(1): \quad \Gamma$ is planar

$(2): \quad \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: $(1) \implies (2)$ and $(2) \implies (1)$.

$(1)$ implies $(2)$

First we consider $K_5$.

$K_5$ has $5$ vertices and $10$ edges.

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.

Suppose we count the incident edge-face pairs.

Then the number of faces is at most:

$E \dfrac 2 3 = 6 \dfrac 2 3$

which contradicts the deduction that $K_5$, if planar, should have $7$ faces.

Hence $K_5$ is non-planar.

Now consider $K_{3, 3}$.

$K_{3, 3}$ has $6$ vertices and $9$ edges.

Hence $K_{3, 3}$ has $5$ faces if it is planar.

Since $K_{3, 3}$ is bipartite, from Graph is Bipartite iff No Odd Cycles, each cycle in $K_{3,3}$ has an even number of edges.

Hence any face must have at least $4$ edges.

So the number of faces is at most

$E \dfrac 2 4 = 4 \dfrac 1 2$

which contradicts the deduction that $K_{3, 3}$, if planar, should have $5$ faces.

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.

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.

Taking the contrapositive:

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

$(2)$ implies $(1)$

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Source of Name

This entry was named for Kazimierz Kuratowski.

Sources

• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Kuratowski's Theorem
• 2021: Richard Earl and James Nicholson: The Concise Oxford Dictionary of Mathematics (6th ed.) ... (previous) ... (next): Kuratowski's Theorem