Planar graph: drawable without crossings. Kuratowski (1930): planar iff no K_5 or K_{3,3} subdivision. Wagner: planar iff no K_5 or K_{3,3} minor. Euler: V-E+F=2 (connected). Corollary: |E|≤3V-6, so planar graphs are sparse.
How to Use
Select graph:
- Planar? Yes/No
- Euler: V-E+F=2
- Bound: |E|≤3V-6
Kuratowski's Theorem
G is planar iff it contains no subdivision of K_5 or K_{3,3}. These are the only two obstructions! K_5 has 5 vertices all connected. K_{3,3} is the utilities problem graph. Both are minimally non-planar.
Four Color Theorem
Every planar graph is 4-colorable: χ≤4. Proved by Appel & Haken (1976) with computer assistance. First major theorem proved by computer. Five color theorem (Heawood, 1890) is much simpler to prove.
Step-by-Step Instructions
- 1Select graph.
- 2Check planarity.
- 3Verify Euler.
- 4Count faces.
- 5Check 4-colorable.