TheoremProved

Kuratowski's theorem

Statement

A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ (the complete graph on 5 vertices) or $K_{3,3}$ (the complete bipartite graph on $3+3$ vertices).

Why is it true?

Every failure of planarity comes down to one of two minimal tangles — five vertices all connected to each other ( $K_5$ ), or three utilities connected to three houses ( $K_{3,3}$ ) — possibly disguised by extra degree-2 vertices inserted along their edges. If neither minimal nonplanar core is hiding inside your graph, the graph can always be drawn in the plane without crossings.

Proof sketch

That $K_5$ and $K_{3,3}$ (and hence their subdivisions) are nonplanar follows from Euler's formula $V - E + F = 2$ : a planar graph on $V \ge 3$ vertices satisfies $E \le 3V - 6$ (ruling out $K_5$ , which has $V=5, E=10$ ) and $E \le 2V - 4$ if triangle-free (ruling out $K_{3,3}$ , which is bipartite with $V=6, E=9$ ). For the converse, take a minimal nonplanar counterexample $G$ , show it is 3-connected, contract or delete an edge $e = \{u,v\}$ and analyze how the paths around the faces of a planar embedding of $G - e$ obstruct placing $e$ without crossings, which forces a subdivision of $K_5$ or $K_{3,3}$ .

Topics that use this theorem

Planar graphs Graphs, degree, and paths

Related theorems

Euler's polyhedron formula

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Casimir Kuratowski (1930). Sur le problème des courbes gauches en Topologie