Online Encyclopedia
Four color theorem
The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same color. Two regions are called adjacent if they share a border segment, not just a point.
The problem itself dates to 1852, when Francis Guthrie , while trying to color the map of counties of England, noticed that four colors sufficed. The first printed reference is due to Arthur Cayley in 1878, "On the colourings of maps.," Proc. Royal Geog. Soc. 1 (1879), 259-261.
It is obvious that three colors are completely inadequate, and it is not difficult to prove that five colors are sufficient to color a map. Significant results in that area were produced by Croatian mathematician Danilo Blanuša in the 1940s by finding an original snark. However, it was not until 1977 that the four-color conjecture was finally proven by Kenneth Appel and Wolfgang Haken. They were assisted in some algorithmic work by J. Koch.
The proof reduced the infinitude of possible maps to 1,936 configurations (later reduced to 1,476) which had to be checked one by one by computer. The work was independently double checked with different programs and computers. In 1996, Neil Robertson , Daniel Sanders , Paul Seymour and Robin Thomas produced a similar proof which required checking 633 special cases. This new proof also contains parts which require the use of a computer and are impractical for humans to check alone.
The four color theorem was the first major theorem to be proven using a computer, and the proof was not accepted by all mathematicians because it could not directly be verified by a human. Ultimately, one had to have faith in the correctness of the compiler and hardware executing the program used for the proof.
The lack of mathematical elegance was another factor, and to paraphrase comments of the time "a good mathematical proof is like a poem—this is a telephone directory!"
| Contents |
Formal statement in graph theory
To formally state the theorem, it is easiest to rephrase it in graph theory. It then states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color. Or "every planar graph is four-colorable" for short. Here, every region of the map is replaced by a vertex of the graph, and two vertices are connected by an edge if and only if the two regions share a border segment.
Generalizations
One can also consider the coloring problem on surfaces other than the plane. The problem on the sphere is equivalent to that on the plane. For closed (orientable or non-orientable) surfaces with positive genus , the maximum number p of colors needed depends on the surface's Euler characteristic χ according to the formula
where the outermost brackets denote the floor function. The only exception to the formula is the Klein bottle, which has Euler characteristic 0 and requires 6 colors. This was initially known as the Heawood conjecture and proved by Gerhard Ringel and J. T. W. Youngs in 1968.
Real world counter examples
In the real world, not all countries are contiguous (e.g. Alaska as part of the US). If the chosen coloring scheme requires that the territory of a particular country must be the same color, four colors may not be sufficient. Conceptually, a constraint such as this enables the map to become non-planar, and thus the four color theorem no longer applies. For instance, consider a simplified map:
In this map, the two regions labeled 'A' belong to the same country, and must be the same color. This map then requires five colors, since the two 'A' regions together are contiguous with four other regions, each of which is contiguous with all the others. If 'A' consisted of three regions, six or more colors might be required; one can construct maps that require an arbitrarily high number of colors.
See Also
References
- Appel, K. and Haken, W., Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989
- O'Connor and Robertson, History of the Four Color Theorem, MacTutor project, http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html
- Saaty and Kainen, The Four Color Problem: Assaults and Conquest (ISBN 0-486-65092-8)
- Robin Thomas, An Update on the Four-Color Theorem, Notices of the American Mathematical Society, Volume 45, number 7 (August 1998)