**
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.