Kuratowski's theorem

Statement

A subdivision of a graph $H$ is a graph that $H$ gives when some edges are replaced by paths with new inner vertices. Let $G$ be a finite graph. Then $G$ is planar if and only if no subgraph of $G$ is a subdivision of $K_5$ or of $K_{3,3}$.

Remarks

One direction is easy: a subdivision of a nonplanar graph is nonplanar, and $K_5$ and $K_{3,3}$ are not planar. Wagner's theorem is a related result: a finite graph is planar if and only if it has neither $K_5$ nor $K_{3,3}$ as a minor.

History

Kazimierz Kuratowski published the theorem in 1930. Orrin Frink and Paul Smith proved it independently in the same year, but they did not publish their proof. Lev Pontryagin reportedly proved it around 1927, and in the Soviet Union it was also known under his name.

Explanations

L1 human

There are exactly two kinds of obstacle to drawing a graph without crossings. A graph is planar unless it contains a copy of $K_5$ or $K_{3,3}$ in which some edges are stretched into paths.