The Four Color Conjecture

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.

Theorem and Proof

Theorem

Using Kempe’s method of color exchanges in so-called Kempe Chains, any counter-example to his proof of the Four Color Conjecture can be properly colored with at most four colors.

Proof

The following proof requires reference to an actual map generally accepted as a counter-example disproving Kempe’s proof. Because of their historical significance, and because of their differences in complexity, the maps by Errera (Fig. 1.0) and Heawood (Fig. 2.0) have been selected as exemplars that exhibit all the properties required of any map offered as a counter-example to Kempe’s proof.

(click on picture for larger view)

One, Two, Three

(click on picture for larger view)

Step 1.
Given any map offered as a counter-example, or “criminal”, as exeplified by the Errera map (Fig. 1.0) or the Heawood map (Fig. 2.0), exchange colors in the R-X chain as shown in Fig. 1.1 and 2.1. Note that the new region X shares boundaries with regions colored P,S,Q, and at most one region colored R.

Step 2.
Now exchange colors in the R-Q chain as shown in Fig. 1.2 and Fig 2.2. Note that region X now shares boundaries with regions colored P,S,Q, and at most one region colored R. It’s important to note that regions colored R and S that share a boundary with region X cannot share a boundary with each other. Nor can they be regions in the same R-S chain.

Step 3.
Since regions colored R and S that share a boundary with region X cannot be regions in the same R-S chain, exchanging colors in the R-S chain as shown in Fig. 1.3 and Fig. 2.3 produces a map in which region X is bounded by regions colored with at most three colors, leaving a fourth color available for coloring region X as shown in Fig. 1.4 and 2.4. Thus proper coloring of the entire map with at most four colors is achieved.

Note: Exchanging colors in the S-X chain as
a first step also leads to a proper solution.

Commentary

COMMENTARY

After spending some fifty-five years in an awkward and fruitless search for a simple solution to the famous “Four Color Conjecture,” and after being intimidated by the counter-examples by Heawood and Errera, the thought came to me that perhaps researchers were concentrating on coloring the wrong region. I wondered what would happen if counter-examples could be re-colored in a way that would produce a new map that could be properly colored using Kempe’s method of color exchanges. To my surprise, I found that an exchange of colors in the R-X, or S-X chain in the above examples would produce a new map that could easily be properly colored using Kempe’s method. Thus my hope that my theorem should be called “Kempe’s Revenge” in that it restores the validity of his approach and provides the final step needed to complete a “pencil and paper” solution to the problem.

In a way, the “McCracken Theorem” turns out to be so simple “that a caveman could do it.” As Paul Harvey might say, “Now you know the rest of the story.”