Suppose you have a map. Let's rule out degeneracies where a country has separate parts (like the continental U.S. and Alaska). Suppose you want to color all countries so they are easy to distinguish. In particular you want to color neighboring countries with different colors. How many colors do you need at most? (Two countries are " neighboring" if they share a border segment that consists of more than one point. If sharing one point was enough to be neighbors you could divide a pie into arbitrarily many slices all of which share the center, requiring as many colors as there are slices).
In 1852, Francis Guthrie wrote to his brother Frederick saying it seemed that four colors were always sufficient, did Frederick know a proof. Frederick asked his advisor Augustus De Morgan. Morgan did not know either. In 1878 the mathematician Arthur Cayley presented the problem to the London Mathematical Society. Less than a year later Alfred Bray Kempe published a paper purporting to show that the conjecture is true. His argument was considered correct until 1890 when Percy John Heawood discovered a flaw. Work by many people continued and the conjecture was finally proved true in 1976 by Kenneth Appel and Wolfgang Haken.
The proof required unprecedented use of computer time and takes up an entire book: Appel and Haken, Every Planar Map is Four Colorable, Contemporary Mathematics, v. 98, American Mathematical Society, 1989, ISBN 0-8218-5103-9. A very readable summary of the history and proof is in Appel and Haken, The Solution of the Four-Color-Map Problem , Scientific American, v. 237 (1977), No. 4, pp. 108-121.
Fine print, your comments, more links, Peter Alfeld, PA1UM
[16-Aug-1996]