The Four Color Theorem

The Four Color Problem dates back to 1852 when Francis Guthrie, while trying
to color the map of counties of England noticed that four colors sufficed. He
asked his brother Frederick if it was true that any map can be colored using
four colors in such a way that adjacent regions (i.e. those sharing a common
boundary segment, not just a point) receive different colors. Frederick
Guthrie then communicated the conjecture to DeMorgan. The first printed
reference is due to Cayley in 1878.

A year later the first `proof' by Kempe appeared; its incorrectness was
pointed out by Heawood 11 years later. Another failed proof is due to Tait in
1880; a gap in the argument was pointed out by Petersen in 1891. Both failed
proofs did have some value, though. Kempe discovered what became known as
Kempe chains, and Tait found an equivalent formulation of the Four Color
Theorem in terms of 3-edge-coloring.

The next major contribution came from Birkhoff whose work allowed Franklin in
1922 to prove that the four color conjecture is true for maps with at most 25
regions. It was also used by other mathematicians to make various forms of
progress on the four color problem. We should specifically mention Heesch who
developed the two main ingredients needed for the ultimate proof -
reducibility and discharging. While the concept of reducibility was studied
by other researchers as well, it appears that the idea of discharging,
crucial for the unavoidability part of the proof, is due to Heesch, and that
it was he who conjectured that a suitable development of this method would
solve the Four Color Problem.

This was confirmed by Appel and Haken in 1976, when they published their
proof of the Four Color Theorem [1,2].


Reference:
http://www.math.gatech.edu/~thomas/FC/fourcolor.html