How Many Colors Do You Need?
Take any map — political boundaries, random regions, abstract patterns. Try to color it so no two neighboring regions share the same color. How many colors do you need? The four color theorem, one of the most famous results in mathematics, guarantees that four colors always suffice for any map on a flat surface. This seemingly simple statement took over a century to prove.
A Conjecture That Stumped Mathematicians
In 1852, Francis Guthrie noticed that four colors seemed sufficient when coloring a map of English counties. His brother passed the question to Augustus De Morgan, and the four color conjecture was born. For 124 years, the best mathematicians attacked the problem. Five colors were proved sufficient in 1890, but closing the gap from five to four seemed impossibly hard.
The Computer-Assisted Proof
In 1976, Kenneth Appel and Wolfgang Haken finally proved the theorem — but their proof required a computer to check 1,936 configurations. This was the first major theorem proved by computer, and it sparked heated debate: is a proof you can't verify by hand really a proof? Today, computer-assisted proofs are commonplace, but the four color theorem was the trailblazer.
Graph Theory and Beyond
The four color theorem is really about graph coloring — assigning colors to vertices of a planar graph so no adjacent vertices share a color. This connects to scheduling problems, register allocation in compilers, frequency assignment in telecommunications, and Sudoku puzzles. On surfaces of higher genus (torus, Klein bottle), more colors may be needed — up to 7 on a torus.