Four Color Map

I first heard about the four-color map theorem in the early 1980's when I was in grad school at the University of Illinois at Urbana-Champaign. When I mentioned to a friend the name of my professor for a math class I was taking, he reminded me of Wolfgang Haken's fame. Just a few years earlier, Haken and a colleague, Kenneth Appel, proved the four-color map theorem. The theorem states for a planar surface, divided into any number and shape of regions, four colors suffice for coloring the regions so no two adjacent regions have the same color. 

In the first, simple checkerboard pattern below, only two colors are needed. However, in the second example, which already has used three colors, the middle region must use a fourth color to satisfy the condition that no adjacent regions have the same color.

Cartographers had known of the restriction for years but no one had been successful in proving the theorem until Haken and Appel in 1976 - published in 1977 in the Illinois Journal of Mathematics.

Haken and Appel's proof was ground-breaking and controversial as it was the first mathematical proof that relied on computer assistance. In their proof, they used mathematical rules to reduce the infinitude of possible map configurations to 1,834 configurations which were then checked one by one by computer.

7/25/2023 Update: Scientific American recently published a history of the four-color map problem: How a Doodler's Problem Sparked a Controversy in Math - Scientific American.

2/6/2024 Update: Quanta Magazine has a video explaining the four-color theorem and the use of computers to establish the proof: How Math’s Famous Map Theorem Was Solved With Computers.