Kuratowski's Theorem

Kuratowski's theorem gives a complete characterization of planarity in terms of two “forbidden” graphs.

Subdivisions

A subdivision of a graph is obtained by repeatedly subdividing edges (replacing an edge by a path by inserting degree-$2$ vertices).

Subdividing edges preserves planarity: a drawing of the original edge can be used as the drawing of the whole path.

Statement

A finite graph is planar iff it contains no subdivision of either $K_5$ or $K_{3,3}$.

Equivalently: a graph is nonplanar iff it contains a “hidden” $K_5$ or $K_{3,3}$ after suppressing degree-$2$ vertices on paths.

How to use it in problems

• To prove nonplanar: explicitly exhibit a subgraph that is a subdivision of $K_5$ or $K_{3,3}$.
• If that’s hard: use Euler bounds first (from Euler's formula) to rule out planarity by counting. Kuratowski is then the “structural” reason behind those obstructions.

In olympiad settings, the most common workflow is:

1. simplify the graph (delete degree-$1$ vertices, suppress degree-$2$ paths),
2. hunt for a $K_5$/$K_{3,3}$ subdivision, or
3. apply Euler's formula bounds if the graph is dense.