Maths WorkshopMaths problems with full solutions
Exercise 2141Combinatorics › Graph theoryL1Added 3 Nov 2026

Kuratowski's theorem (statement)

#Kuratowski#planarity#minors

Statement

State Kuratowski's theorem characterizing planar graphs.

Hint

A graph is planar iff it contains no subdivision of K5K_5 or K3,3K_{3,3}.

Show solutionHide solution

Solution

Theorem. A graph is planar iff it contains no subgraph that is a subdivision of K5K_5 or K3,3K_{3,3}.

Equivalent. A graph is planar iff it has no minor isomorphic to K5K_5 or K3,3K_{3,3} (Wagner's form).

Conclusion. These are the two fundamental obstructions to planarity.