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 1852. 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 assertion for map coloring, showing that in
a genus 0 space (including the
sphere or plane), four colors
suffice. Ringel and Youngs (1968) proved that for
genus ,
the upper bound provided by the Heawood conjecture
also give the necessary number of colors, with the
exception of the Klein bottle (for which the Heawood
formula gives seven, but the correct bound is six).
Six colors can be proven to suffice for the case, and this number can easily be reduced to five, but
reducing the number of colors all the way to four proved very difficult. This result
was finally obtained by Appel and Haken (1977), who constructed 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 shorter, independent proof was constructed by Robertson
et al. (1996; Thomas 1998).
In December 2004, G. Gonthier of Microsoft Research in Cambridge, England (working with B. Werner of INRIA in France) announced that they had verified the Robertson
et al. proof by formulating the problem in the equational logic program Coq
and confirming the validity of each of its steps (Devlin 2005, Knight 2005).
J. Ferro (pers. comm., Nov. 8, 2005) has debunked a number of purported "short" proofs of the four-color theorem.
Martin Gardner (1975) played an April Fool's joke by asserting that the McGregor map consisting of 110 regions required five colors and constitutes a counterexample
to the four-color theorem.
Appel, K. and Haken, W. "Every Planar Map is Four-Colorable, II: Reducibility." Illinois J. Math.21, 491-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. "The
Four Color Proof Suffices." Math. Intell.8, 10-20 and 58, 1986.Appel,
K. and Haken, W. Every
Planar Map is Four-Colorable. Providence, RI: Amer. Math. Soc., 1989.Appel,
K.; Haken, W.; and Koch, J. "Every Planar Map is Four Colorable. I: Discharging."
Illinois J. Math.21, 429-490, 1977.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.52,
283-289, 1959.Devlin, K. "Devlin's Angle: Last Doubts Removed About
the Proof of the Four Color Theorem." Jan. 2005.Errera, A.
Du colorage de cartes et de quelques questions d'analysis situs. Ph.D. thesis.
Paris: Gauthier-Villars, 1921.Franklin, P. "Note on the Four Color
Problem." J. Math. Phys.16, 172-184, 1937-1938.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-132, Apr. 1975.Gardner, M. "Mathematical
Games: On Tessellating the Plane with Convex Polygons." Sci. Amer.232,
112-117, Jul. 1975.Gardner, M. The
Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications. New
York: Springer-Verlag, p. 86, 1997.Gethner, E. and Springer, W. M.
II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer.164,
159-175, 2003.Harary, F. "The Four Color Conjecture." Graph
Theory. Reading, MA: Addison-Wesley, p. 5, 1994.Heawood,
P. J. "Map Colour Theorems." Quart. J. Math.24, 332-338,
1890.Heawood, P. J. "On the Four-Color Map Theorem."
Quart. J. Pure Math.29, 270-285, 1898.Hutchinson, J. P.
and Wagon, S. "Kempe Revisited." Amer. Math. Monthly105,
170-174, 1998.Kempe, A. B. "On the Geographical Problem of
Four-Colors." Amer. J. Math.2, 193-200, 1879.Kittell,
I. "A Group of Operations on a Partially Colored Map." Bull. Amer. Math.
Soc.41, 407-413, 1935.Knight, W. "Computer Generates
Verifiable Mathematics Proof." New Scientist Breaking News. Apr. 19,
2005.Kraitchik, M. §8.4.2 in Mathematical
Recreations. New York: W. W. Norton, p. 211, 1942.May,
K. O. "The Origin of the Four-Color Conjecture." Isis56,
346-348, 1965.Morgenstern, C. and Shapiro, H. "Heuristics for Rapidly
4-Coloring Large Planar Graphs." Algorithmica6, 869-891, 1991.Ore,
Ø. The
Four-Color Problem. New York: Academic Press, 1967.Ore, Ø.
and Stemple, G. J. "Numerical Methods in the Four Color Problem."
Recent Progress in Combinatorics (Ed. W. T. Tutte). New York: Academic
Press, 1969.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.Ringel, G. and Youngs, J. W. T. "Solution of the
Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA60, 438-445,
1968.Robertson, N.; Sanders, D. P.; Seymour, P. D.; and Thomas,
R. "A New Proof of the Four Colour Theorem." Electron. Res. Announc.
Amer. Math. Soc.2, 17-25, 1996.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.Skiena,
S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, p. 210, 1990.Steinhaus, H. Mathematical
Snapshots, 3rd ed. New York: Dover, pp. 274-275, 1999.Tait,
P. G. "Note on a Theorem in Geometry of Position." Trans. Roy.
Soc. Edinburgh29, 657-660, 1880.Thomas, R. "An Update
on the Four-Color Theorem." Not. Amer. Math. Soc.45, 858-857,
1998.Weisstein, E. W. "Books about Four-Color Problem."
http://www.ericweisstein.com/encyclopedias/books/Four-ColorProblem.html.Wells,
D. The
Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England:
Penguin Books, p. 57, 1986.Wells, D. The
Penguin Dictionary of Curious and Interesting Geometry. London: Penguin,
pp. 81-82, 1991.Wilson, R. Four
Colors Suffice : How the Map Problem Was Solved. Princeton, NJ: Princeton
University Press, 2004.
,
the upper bound provided by the Heawood conjecture
also give the necessary number of colors, with the
exception of the Klein bottle (for which the Heawood
formula gives seven, but the correct bound is six).
case, and this number can easily be reduced to five, but
reducing the number of colors all the way to four proved very difficult. This result
was finally obtained by Appel and Haken (1977), who constructed 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 shorter, independent proof was constructed by Robertson
et al. (1996; Thomas 1998).
