Kuratowski Theorem

Kuratowski's theorem (1930) provides a complete characterization of planar graphs through forbidden substructures, one of the most elegant results in graph theory.

TheoremKuratowski's Theorem

A graph $G$ is planar if and only if it contains no subgraph homeomorphic to $K_5$ or $K_{3,3}$ .

Equivalently, $G$ is non-planar if and only if it contains a subdivision of $K_5$ or $K_{3,3}$ .

The two forbidden graphs $K_5$ and $K_{3,3}$ are minimal non-planar: they cannot be drawn without crossings, but removing any edge makes them planar.

ProofProof Sketch

( $\Leftarrow$ ) If $G$ contains a $K_5$ or $K_{3,3}$ subdivision, then $G$ is non-planar since subdivisions preserve planarity and $K_5$ , $K_{3,3}$ are non-planar (provable via Euler's formula).

( $\Rightarrow$ ) The hard direction: if $G$ is non-planar, it must contain such a subdivision. Proof by induction on vertices and edges, using structural decomposition. Key insight: any non-planar graph can be reduced to one of these two configurations through edge contractions and deletions while maintaining non-planarity.

■

ExamplePetersen Graph

The Petersen graph is non-planar. It contains a $K_{3,3}$ subdivision as a subgraph. By identifying specific vertices and paths, we can extract a homeomorphic copy of $K_{3,3}$ , proving non-planarity via Kuratowski's theorem.

Remark

Wagner's Theorem (1937) provides an equivalent characterization using graph minors: $G$ is planar if and only if it has no $K_5$ or $K_{3,3}$ minor (minor obtained by edge deletion and contraction). This minor-based perspective led to the deep Graph Minor Theory developed by Robertson and Seymour.