Course contentsShow
← Mathematics
Lesson 2697 of 3,12153. Graph TheoryFree lesson

The Four Color Theorem

State the Four Color Theorem: every planar graph can be properly colored with at most four colors.

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.