Four Colors Can Do It

The question as to the possibility of coloring every normal planar map with at most four colors was first raised in 1852 by Francis Guthrie, who while trying to color the map of counties of England, noticed that four colors would suffice. He asked his brother Frederick if it was true that any map could be colored with at most four colors in such a way that no two regions of the same color would share a common boundary. In response, Frederick Guthrie and others formulated the conjecture and the first printed reference was offered by Arthur Caley in 1878.

A year later Alfred Kempe published a “proof” using a method of color exchanges in what have becomeknown as “Kempe Chains”. Kempe’s proof stood for eleven years until Percy Heawood offered a map that was accepted as a counter-example that exposed a perceived flaw in Kempe’s work. In 1921 Alfred Errera produced a less complicated counter-example, or “minimal criminal” which was also accepted as proof that Kempe’s method could not be used to properly color all maps with at most four colors.

For some reason, the validity of the Heawood and Errera maps has remained unchallenged until the present. However, the following theorem proves that, using Kempe’s method, the Heawood and Errera maps, and by extension any counter-example, can be properly colored with at most four colors.