The Four Color Problem

This is an interesting mathematical conjecture that was open for a century and then "solved" in the 1970s by Ken Appel and Wolfgang Haken with a considerable amount of computer assistance. This is an interesting topic for a paper as it deals with an easily understood problem of some real world significance. It is the kind of problem that made the newspapers when the solution was announced. Another aspect, and a controversial one, is whether such a long computer-aided proof is really a proof. Thus this is an interesting issue in the philosophy of mathematics.

Here are a few references to get you started. Be careful to treat the chronologically earlier references with care.

Appel, Kenneth, and Haken, Wolfgang, "The solution of the four-color-map problem," Scientific American, Oct 1977, 108-121. Look at the back of the issue for further references and at the front for information about the authors (you should always do this when reading Scientific American).
Biggs, Norman L, et al., Graph Theory 1736-1936.
Coxeter, H. M. S., "Map coloring problems," Scripta Mathematica, Franklin, Philip, "The four color problem," Scripta Mathematica, 6(1939), 149-156 and 197-210.
May, Kenneth O., "The origin of the four-color conjecture," Isis 56(1965), 346-348.
Tymoczko, Thomas, "Computes, proofs and mathematicians: A philosophical investigation of the four-color proof," Mathematics Magazine, 53(1980), 131-138. This is a follow up on a paper Tomoczko published in a major philosophical journal. It caused a big controversy about the nature of mathematical proof that has not subsided. Be sure to follow up this line.
Wilson, Robin, Four Colors Suffice: How the Map Problem Was Solved, Princeton University Press, ISBN: 0691115338, (March 2003).

If you have access to MathSciNet then you will find the entire technical literature on this topic.

Return to the minicourse home page.
If you have comments, send email to V. Frederick Rickey at fred-rickey@usma.edu .

Last revised 4 January 2003.