Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

Multivariate Splines and the 4 Color Map Problem


The above history is very concise! Kempe's "proof " was accepted as valid for eleven years. This is a prime example in the history of mathematics that a flaw was found in a proof that had passed muster and had been generally accepted.

Real maps can be more complicated than the maps considered in the four color map problem. We must assume that countries are connected (unlike the US, for example). Otherwise one could easily construct maps where four colors do not suffice (here is an exercise for you). We also assume that countries don't have holes. To be neighbors countries must meet along line segments (otherwise one could easily construct pie like maps with many countries meeting at the center, and requiring as many colors as there are countries).

While flawed, Kempe's ideas were extremely clever and subtle, and they established the strategies that ultimately succeeded.

Kempe showed correctly that any map requiring colors must contain at least one country with a total number of 3, 4, or 5 neighbors. He then proceeded to show that for each such configuration the map can be replaced by another map with fewer countries that also requires five colors. His argument for the country with five neighbors was flawed.

The most complete reference on the four color map problem is the book referenced on the slide,. but much more readable, particularly for a general reader, is the survey:

Appel and Haken, The Solution of the Four-Color-Map Problem, Scientific American, v. 237 (1977), No. 4, pp. 108-121.