The four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent if they share a common boundary that is not a corner, where corners are the points shared by three or more regions.
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 receive different colors. Frederick Guthrie then communicated the conjecture to DeMorgan. The first printed reference is due to Cayley in 1878.
Martin Gardner wrote a popular account of what was known at the time about the four color theorem in his September 1960 Mathematical Games column in Scientific American magazine. In 1975 Gardner revisited the topic by publishing a map said to be a counter-example in his infamous April fool's hoax column of April 1975.
Appel and Haken in 1976, published their proof of the Four Color Theorem.
There are two reasons why the Appel-Haken proof is not completely satisfactory. Part of the Appel-Haken proof uses a computer, and cannot be verified by hand, and even the part that is supposedly hand-checkable is extraordinarily complicated and tedious, and as far as we know, no one has verified it in its entirety.
They have tried to verify the Appel-Haken proof, but soon gave up. Checking the computer part would not only require a lot of programming, but also inputing the descriptions of 1476 graphs, and that was not even the most controversial part of the proof. They decided that it would be more profitable to work out our own proof. So they did and came up with a proof and an algorithm that are described below.