4.7/5 - (64 votes)

In 1976, two mathematicians announced that four colors are enough to shade any map. The proof leaned on more than a thousand hours of computer time, and part of the math world was not sure it counted as a proof at all.

A student noticed it while coloring English counties

The question is usually dated to October 23, 1852. Francis Guthrie was coloring a map of the counties of England when he noticed that four colors always seemed to be enough, as long as no two neighboring regions shared one.

He asked his brother Frederick, a student of Augustus De Morgan in London, who passed it on. De Morgan admitted he could not answer it. He wrote that a student had asked him for a reason for “a fact which I did not know was a fact, and do not yet.”

Two famous proofs, both wrong

In 1879, Alfred Kempe published a proof that was widely acclaimed. A year later, Peter Guthrie Tait offered another. Both stood for 11 years.

In 1890, Percy Heawood exposed the flaw in Kempe’s argument. In 1891, Julius Petersen did the same to Tait’s. Heawood salvaged something, though: he proved that five colors always suffice.

Kempe’s failed proof was not wasted. Its basic tools, such as chains of alternating colors and the idea of shrinking a map by removing a piece, ended up inside the proof that finally worked.

The proof that no human could check

In the 1960s and 1970s, Heinrich Heesch developed ways to use computers in the hunt, but he could not get the supercomputer time he needed. On June 21, 1976, Kenneth Appel and Wolfgang Haken at the University of Illinois announced they had done it.

See also  A 1924 proof says you can cut up a pea and rebuild the Sun

Their trick was to show that a smallest map needing five colors could not exist. They found a set of 1,834 map patterns (later cut to 1,482) that any such map would have to contain, then checked by computer that each one could be shrunk to a smaller map. That check took over a thousand hours.

The other half of the argument was checked by hand. It filled more than 400 pages of microfiche, and Haken’s daughter Dorothea Blostein helped go through it.

Is a proof still a proof if you cannot read it?

The news traveled the world. The Illinois math department even stamped its outgoing mail with the postmark “Four colors suffice.” The New York Times refused as a matter of policy to report on it, fearing the proof would be shown false like the earlier ones.

Inside mathematics, the reaction was split. Ian Stewart found it unsatisfying and wrote that “the answer appears as a kind of monstrous coincidence.” H. S. M. Coxeter thought it “very unlikely that anyone can break that proof down into something that one would regard as an ordinary proof.”

Then came the rumors. In the early 1980s, Ulrich Schmidt checked about 40 percent of the hand-verified part for his master’s thesis and found a significant error. Appel and Haken said the rumors came from a misreading, and in 1989 published a book that explained and corrected that error along with several others found by other people.

Trusting the computer less and less

In 1996, Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas built a cleaner version that needed only 633 patterns. It is still far too long for a person to verify by hand. In 2005, Benjamin Werner and Georges Gonthier went further and had the proof checked inside the Coq proof assistant, so that only the small core of that software had to be trusted rather than every program used along the way.

See also  5 facts about symmetry that stretch from ancient bronze to modern physics

A theorem that mapmakers never needed

There is an irony. Historian Kenneth May pointed out that maps using only four colors are rare, and the ones that do usually need just three. Books on mapmaking, he noted, do not mention the four-color property. The theorem also says nothing about countries with separate pieces, like Alaska, that must share one color.

What the 1976 result really changed was not cartography. It made mathematicians ask a question that has never fully gone away: when a machine does the checking, what does it mean to know something is true?