The Four Color Theorem
What You'll Learn
You'll discover one of the most famous results in graph theory: that any planar graph (or map) can be properly colored using just four colors.
The Statement
The Four Color Theorem states that every planar graph can be properly colored with at most four colors. In other words, you can assign one of four colors to each vertex so that no two adjacent vertices share the same color.
Understanding the Theorem
Think of coloring a geographical map where each region is a vertex and two regions are connected (adjacent) if they share a border. The Four Color Theorem guarantees that no matter how complicated your map is, you never need more than four colors to ensure bordering regions have different colors.
This is remarkable because:
- Some planar graphs need exactly 4 colors (you can't always get away with 3)
- No planar graph ever needs a 5th color, no matter how complex
- The chromatic number of any planar graph is at most 4: χ(G) ≤ 4
Historical Significance
This theorem was conjectured in 1852 but wasn't proven until 1976 by Kenneth Appel and Wolfgang Haken. Their proof was controversial because it relied heavily on computer verification of thousands of special cases—one of the first major theorems proved with computational assistance.
Practical Interpretation
When you studied graph coloring and chromatic numbers, you learned that different graphs require different numbers of colors. The Four Color Theorem sets a definitive upper bound for planar graphs, which is tremendously useful in applications like map design, frequency assignment in wireless networks, and scheduling problems.
Key Takeaway: Every planar graph has chromatic number χ(G) ≤ 4, meaning four colors always suffice for proper vertex coloring.