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 or .
Show solutionHide solution
Solution
Theorem. A graph is planar iff it contains no subgraph that is a subdivision of or .
Equivalent. A graph is planar iff it has no minor isomorphic to or (Wagner's form).
Conclusion. These are the two fundamental obstructions to planarity.