Color a map so that no two countries sharing a border get the same color, and four shades always seem to be enough. Guthrie conjectured it in 1852 and the problem passed through de Morgan into the wider community. Six colors were provable, and five, but four resisted for over a century.
Four, and the proof needed a computer. Appel and Haken constructed the first in 1977, whose exhaustive analysis of many discrete cases initially made independent verification difficult. A shorter independent proof came from Robertson and colleagues in 1996, and Gonthier produced a machine-checked version in 2004.
The four-color theorem states that every finite with no self-loops has a proper vertex coloring using at most four colors. Put as a map, the faces of a finite plane graph can be colored so that distinct regions sharing a boundary arc have different colors.
The question is old and the false starts are famous. F. Guthrie conjectured it in 1852 and the problem reached the wider community through de Morgan. Cayley wrote the first paper on it in 1878, and followed from Kempe in 1879 and Tait in 1880.
Kempe’s stood for ten years. Heawood then showed the error with a map of 25 regions, although a map with nine regions is enough to expose the flaw, and the problem was open again.
Reducing the count proved brutally hard. Six colors could be shown to suffice and the number came down to five easily enough, but four held out. It required the computer-assisted proof of Appel and Haken in 1977, a shorter independent proof by Robertson and colleagues in 1996, and a machine-checked proof by Gonthier in 2004. The had already shown four to be enough in a genus zero space.
wat. A hundred and twenty-five years from guess to proof, and the proof was a program.
wat wat
It was the first famous theorem whose proof nobody could check by hand, which changed what a proof is allowed to be.
How do we know?
Wolfram MathWorld states the theorem in graph terms, traces the conjecture from Guthrie through the failed proofs, and lists the successive proofs and their verification.
What is still unknown
The theorem covers finite planar graphs, and contact at only finitely many boundary points does not count as adjacency.
Learn something?
Where to next
How many colors does it take to color any map?proof
Did Alan Turing really prove the halting problem attributed to him?proof
Why is there always one point in the coffee that did not move?proof