Kuratowski's Theorem

Graph Theory · Axiom Academy

A fundamental characterization of planar graphs through forbidden subgraphs Kuratowski's Theorem states that a graph is planar if and only if it contains no subdivision of K₅ (the complete graph on 5 vertices) or K₃,₃ (the complete bipartite graph with parts of size 3). These two graphs, K₅ and K₃,₃, are the minimal non-planar graphs. They serve as the fundamental obstructions to planarity. A subdivision of a graph is obtained by replacing edges with paths. More formally, we insert additional vertices of degree 2 along existing edges, dividing them into sequences of edges. Subdivisions preserve the essential topological structure of a graph. If you can't draw K₅ without crossings, you also can't draw any subdivision of K₅ without crossings. K₅ and K₃,₃ are the two fundamental non-planar graphs. Understanding why they cannot be drawn in the plane helps us identify non-planarity in more complex graphs. K₅ has 5 vertices with all possible edges (10 edges total). By Euler's formula, a planar graph with 5 vertices can have at most 10 edges, but the complete structure forces crossings. K₃,₃ is bipartite with 6 vertices (3 in each part) and 9 edges. It contains no triangles, yet its structure forces crossings when drawn in the plane. 4. Using the Contrapositive to Prove Non-Planarity The contrapositive of Kuratowski's Theorem is especially useful: If G contains a subdivision of K₅ or K₃,₃, then G is non-planar.

This is the written version of the interactive lesson above. See the full Graph Theory course.