Four-Color Theorem

The four-color theorem states that any map in a Plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. This problem is sometimes also called Guthrie's Problem after F. Guthrie, who first conjectured the theorem in 1853. The Conjecture was then communicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on the conjecture.

Fallacious proofs were given independently by Kempe (1879) and Tait (1880). Kempe's proof was accepted for a decade until Heawood showed an error using a map with 18 faces (although a map with nine faces suffices to show the fallacy). The Heawood Conjecture provided a very general result for map coloring, showing that in a Genus 0 Space (i.e., either the Sphere or Plane), six colors suffice. This number can easily be reduced to five, but reducing the number of colors all the way to four proved very difficult.

Finally, Appel and Haken (1977) announced a computer-assisted proof that four colors were Sufficient. However, because part of the proof consisted of an exhaustive analysis of many discrete cases by a computer, some mathematicians do not accept it. However, no flaws have yet been found, so the proof appears valid. A potentially independent proof has recently been constructed by N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas.

Martin Gardner (1975) played an April Fool's joke by (incorrectly) claiming that the map of 110 regions illustrated below requires five colors and constitutes a counterexample to the four-color theorem.

$\begin{figure}\begin{center}\BoxedEPSF{FourColor.epsf}\end{center}\end{figure}$

References

Four-Color Problem

Appel, K. and Haken, W. ``Every Planar Map is Four-Colorable, I and II.'' Illinois J. Math. 21, 429-567, 1977. Appel, K. and Haken, W. ``The Solution of the Four-Color Map Problem.'' Sci. Amer. 237, 108-121, 1977.

Appel, K. and Haken, W. Every Planar Map is Four-Colorable. Providence, RI: Amer. Math. Soc., 1989.

Barnette, D. Map Coloring, Polyhedra, and the Four-Color Problem. Providence, RI: Math. Assoc. Amer., 1983.

Birkhoff, G. D. ``The Reducibility of Maps.'' Amer. Math. J. 35, 114-128, 1913.

Chartrand, G. ``The Four Color Problem.'' §9.3 in Introductory Graph Theory. New York: Dover, pp. 209-215, 1985.

Coxeter, H. S. M. ``The Four-Color Map Problem, 1840-1890.'' Math. Teach., Apr. 1959.

Franklin, P. The Four-Color Problem. New York: Scripta Mathematica, Yeshiva College, 1941.

Gardner, M. ``Mathematical Games: The Celebrated Four-Color Map Problem of Topology.'' Sci. Amer. 203, 218-222, Sep. 1960.

Gardner, M. ``The Four-Color Map Theorem.'' Ch. 10 in Martin Gardner's New Mathematical Diversions from Scientific American. New York: Simon and Schuster, pp. 113-123, 1966.

Gardner, M. ``Mathematical Games: Six Sensational Discoveries that Somehow or Another have Escaped Public Attention.'' Sci. Amer. 232, 127-131, Apr. 1975.

Gardner, M. ``Mathematical Games: On Tessellating the Plane with Convex Polygons.'' Sci. Amer. 232, 112-117, Jul. 1975.

Kempe, A. B. ``On the Geographical Problem of Four-Colors.'' Amer. J. Math. 2, 193-200, 1879.

Kraitchik, M. §8.4.2 in Mathematical Recreations. New York: W. W. Norton, p. 211, 1942.

Ore, Ø. The Four-Color Problem. New York: Academic Press, 1967.

Pappas, T. ``The Four-Color Map Problem: Topology Turns the Tables on Map Coloring.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 152-153, 1989.

Robertson, N.; Sanders, D. P.; and Thomas, R. ``The Four-Color Theorem.'' http://www.math.gatech.edu/~thomas/FC/fourcolor.html.

Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, 1986.

Tait, P. G. ``Note on a Theorem in Geometry of Position.'' Trans. Roy. Soc. Edinburgh 29, 657-660, 1880.