Four Colors Suffice: How the Map Problem Was Solved [Hardcover]

Surprisingly, mapmakers aren't very interested in the problem. It was first mentioned in writing in 1852, and in 1879, Alfred Kempe published one of the most famous proofs in mathematics, famous because it proved the theorem and famous because, although it was accepted for about a decade, it was wrong. Kempe's work was useful, as it was an attack on the problem that others eventually used in different ways, but it did not stand. Percy Heawood published a paper in which he included a diagram that Kempe's method could be used on and for which Kempe's method failed. (Not that more than four colors were needed for the map; it simply showed Kempe's method didn't cover all possibilities.) Heawood built on Kempe's work to prove a five color map theorem, but the four color version proved elusive. There was so much data developed in proofs in the 1960s that computers became essential to handle them. Wolfgang Haken worked on the theorem, and was told by computer experts that his ideas could not be programmed, but programmer Kenneth Appel disagreed. In 1972, Haken and Appel teamed up to work on a computer-aided solution, and in 1976, they announced it. They were rushing, as other map-colorers were coming close to a solution themselves. The proof required a thousand hours of computer time, a hundred pages of summary, a hundred pages of detail, and seven hundred pages of back-up work. The computer printouts for it stacked to four feet high. The long hunt was over, but it was not satisfactory to everyone. The problem is that the computer did so much work on the proof that humans cannot check everything the computer did; some mathematicians, especially older ones, have not accepted this proof, although no significant error has been found.

_Four Colors Suffice_ not only explains the theorem and historic attempts at proofs in a clear fashion, it is an inspiring look at something that is really rather lovable in our species, the pursuit of mathematical knowledge for its own sake. To be sure, the theorem does have practical interest, if not to actual mapmakers, then to road, rail, and communications networks, but it has mainly inspired other aspects of pure mathematics like graph theory and algorithms. There are many stories of cooperation between mathematicians here that make the final conquest of the problem seem like a team effort that has been conducted for over a century. One example: when Haken and Appel needed referees to check their paper, one of them was a mathematician who was bitterly disappointed that his own proof had not scooped them. His work as a referee proved to be conscientious and constructive. This may be a tale of a proof that only a computer could crack, but it is a handsome human success story.