The four-color problem is a long-standing problem that dates back to 1852 when Francis Guthrie, while trying to color a map of the counties of England noticed that four colors were enough to ensure that no adjacent counties were colored the same. He asked his brother Frederick if it was true that any map could be colored using four colors in such a way that adjacent regions (i.e. those sharing a common boundary segment, not just a point) receive different colors. Frederick Guthrie then passed on the conjecture to Augustus de Morgan.

 

The first printed reference is due to Arthur Cayley in 1878. A year later the false "proof," by the English barrister Alfred Kempe, appeared; its incorrectness was pointed out by Percy Heawood 11 years later. Another failed proof is due to Peter Tait in 1880, a gap in his argument being pointed out by Julius Petersen in 1891. Both false proofs did have some value, though. Kempe discovered what became known as Kempe chains, and Tait found an equivalent formulation of the Four-Color Theorem in terms of three-edge coloring.

 

The next major contribution came from George Birkhoff whose work allowed Philip Franklin in 1922 to prove that the Four-Color Conjecture is true for maps with at most 25 regions. It was also used by other mathematicians to make various forms of progress on the Four-Color Problem. The German mathematician Heinrich Heesch, notably, developed the two main ingredients needed for the ultimate proof – reducibility and discharging. While the concept of reducibility was studied by other researchers as well, it seems that the idea of discharging, crucial for the unavoidability part of the proof, is due to Heesch, and that it was he who conjectured that a suitable development of this method would solve the Four-Color Problem. This was confirmed by Kenneth Appel and Wolfgang Haken of the University of Illinois in 1976, when they published their proof of the Four-Color Theorem.¹ Their controversial proof challenges the basic assumptions of what mathematical proof is. They used more than 1,200 hours of supercomputer time to analyze 1,478 different configurations that in turn can produce every possible map on a plane. Not everyone was happy with the method of the breakthrough, as Appel himself pointed out:

 

For almost a century and a half, a Holy Grail of graph theory has been a simple incisive proof of the Four Color Theorem. It has troubled our profession that a problem that can be understood by a school child has yet to be solved in a way that better illuminates the reason that only four colors are needed for planar maps. The feelings of many mathematicians were summed up for me by Herb Wilf's response to being told that it appeared that one could prove the theorem by a long reducibility argument which used computers to test the reducibility of a large number of configurations. He simply said, "God would not allow such a beautiful theorem to have such an ugly proof."

 

Martin Gardner commented, "Whether a simple, elegant proof not requiring a computer will ever be found, is still an open question." It's interesting that such a simple, intuitive puzzle can be so difficult to settle! The Four-Color theorem is true for maps on a plane or on a sphere. The answer is different for geographic maps on a torus: in this case, seven colors are necessary and sufficient.

 

Twelve-Color Map Problem

It has been hyppothesized that if on a plane or spherical map each country has at the most one colony, requiring the same color as its parent country, at most 12 different colors are needed to distinguish the political regions on a map. The problem of determining if this is true or not remain opens.

 

References

1. Appel, K. and Haken, W. "The Solution of the Four-Color Map Problem." Scientific American, 237: 108–121 (1977).
2. Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, 1986.