Kuratowski's Theorem and Graph Subdivisions
What you'll learn: You'll discover a powerful theorem that precisely characterizes which graphs can be drawn on a plane without edge crossings.
The Core Idea
After learning that K₅ and K₃,₃ are the smallest non-planar graphs, you might wonder: are these the only obstructions to planarity? Kuratowski's Theorem answers with a resounding insight.
First, understand graph subdivision: you subdivide a graph by inserting new vertices along existing edges. For example, replacing edge (u,v) with a path u→w→v subdivides that edge. Think of it like adding waypoints on a road—the route is still there, just with extra stops.
Kuratowski's Theorem
The theorem states: A graph is planar if and only if it contains no subdivision of K₅ or K₃,₃ as a subgraph.
In plain English: a graph can be drawn without crossings precisely when you can't find a "stretched-out" copy of K₅ or K₃,₃ hiding within it.
Why This Matters
This theorem gives us a complete characterization of planarity. It's not just that K₅ and K₃,₃ themselves are problematic—any graph that contains their "essence" (via subdivision) is also non-planar. The subdivisions preserve the fundamental topological structure that causes crossings.
Analogy: Think of K₅ and K₃,₃ as genetic markers for non-planarity. Even if you insert extra vertices (like adding segments to DNA), the fundamental "non-planar gene" remains, and the graph still can't be drawn flat.
Practical Use
To prove a graph is non-planar using Kuratowski's Theorem, find a subgraph that's a subdivision of K₅ or K₃,₃. Conversely, if you can show no such subdivision exists, the graph must be planar.
Key Takeaway: Kuratowski's Theorem elegantly reduces the planarity question to detecting subdivisions of exactly two forbidden structures: K₅ and K₃,₃.