K₅ and K₃,₃ are Non-Planar
What you'll learn: You'll prove that two famous graphs—K₅ (five vertices all connected) and K₃,₃ (complete bipartite with 3+3 vertices)—cannot be drawn on a plane without edges crossing.
The Core Idea
A planar graph can be drawn on a flat surface with no edge crossings. Some graphs, however, are inherently non-planar: no matter how cleverly you arrange the vertices, crossings are unavoidable. K₅ and K₃,₃ are the two fundamental examples.
Proving K₅ is Non-Planar
The complete graph K₅ has 5 vertices and every pair is connected, giving us 10 edges.
Using Euler's Formula (v - e + f = 2) and the consequence that for simple planar graphs with ≥3 vertices, e ≤ 3v - 6:
- v = 5, so maximum edges = 3(5) - 6 = 9 edges
- K₅ has 10 edges, which exceeds the bound
- Therefore, K₅ cannot be planar
Proving K₃,₃ is Non-Planar
K₃,₃ is a bipartite graph with 3 vertices in each partition, fully connected across: 6 vertices, 9 edges.
For bipartite planar graphs (which have no triangles, only cycles of length ≥4), a stricter inequality holds: e ≤ 2v - 4:
- v = 6, so maximum edges = 2(6) - 4 = 8 edges
- K₃,₃ has 9 edges, which exceeds the bound
- Therefore, K₃,₃ cannot be planar
Why This Matters
These two graphs are the "minimal obstructions" to planarity. Kuratowski's Theorem (beyond our current scope) states that any non-planar graph contains a subdivision of K₅ or K₃,₃—making them the fundamental building blocks of non-planarity.
Key Takeaway: K₅ and K₃,₃ are provably non-planar because they have too many edges relative to their vertices to satisfy the constraints imposed by Euler's formula and planar graph theory.