Introduction
How many colors do we need to color the countries of a map in such a way that adjacent countries are colored differently?
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 then 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).
In 1977, Appel and Haken 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 potentially independent proof has recently been constructed by N. Robertson, D. P. Sanders, P. D. Seymour, and R. Thomas which also has yet to be verified.
Kempe's attempted proof of the four-color theorem was no a complete failure however. His proof, using the notion of Kempe Chains, was actually a proof of the five-color theorem, that any planar map is 5-colorable.