Color the regions of a map so that no two sharing a border get the same color. A student asked his teacher about it in 1852, and the answer looked obvious enough that proving it should have taken an afternoon. It took 124 years. What finally settled it?
A computer did, which is the part that still provokes an argument. Four colors always suffice, and Appel and Haken reached that in 1976 by building a set of roughly 1,500 that any map must contain, then checking every one of them. The checking ran for 1,200 hours of computer time, and no person can follow it line by line.
Francis Guthrie, a student in London, showed his brother some results about coloring maps and asked him to put the question to De Morgan. On the same day in October 1852, De Morgan wrote to Hamilton in Dublin saying a student had asked him for a reason for a fact he did not know was a fact.
The next century was a sequence of near misses. Kempe announced a proof in Nature in 1879, and Heawood showed in 1890 that it had a defect in it, which returned the theorem to being a conjecture. Others proved it for maps with a limited number of regions, a limit that crept up to 95 regions by 1976.
The pieces came from elsewhere. Heesch introduced in 1969, and Appel and Haken combined it with reducibility using , modifying their unavoidable set and their discharging procedure together until the two matched. Their final set held about 1,500 configurations, each with a boundary of fourteen regions or less.
Then the machine ran for 1,200 hours of computer time, with Koch assisting on the calculations, and the details appeared in two articles in 1977. It was the first major theorem proved with a computer, and its proof cannot be verified directly by a person, which is a different kind of knowing than mathematics had before.
wat. Four colors are always enough, and the shortest known argument for it runs through about 1,500 configurations.
wat wat
It was the first major theorem whose proof no human can verify directly, which forced mathematicians to decide what they will accept as a proof.
How do we know?
They worked from reducibility using Kempe chains, carried through the discharging method Heesch had introduced, and kept the boundary ring size of each configuration down to fourteen or less so the cases stayed checkable.
What is still unknown
Mathematicians still have no short proof that a person can follow from end to end, and every known proof leans on machine checking of many cases.
Learn something?
Where to next
How many colors does any map need?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