The Journey of the Four Color Theorem

1 ▪ Journey through genius

Topical Paper:

The Journey of the Four Color Theorem

First Draft

by Leah Grant

for partial completion of

MATH 4010

Dr. Cherowitzo

21 April 2005

1 ▪ Journey through genius

13

Chapter

Mathematicians

and Map Coloring

(1852 – Present)

Introduction

Although an ostensibly simplistic concept, the Four Colour Conjecture has been quite a difficult one to prove. Escaping both expert mathematicians and amateur enthusiasts, it was not until more than 100 years after its alleged proposition that an accepted proof was completed. In the following discussion we will address the individuals surrounding the Four Color Theorem and their respective contributions to its solution, state the current standing and views on the problem, and discuss some philosophical implications of its fairly recent computer-aided proofs.

What is the Four Color Theorem?

Maps in general serve to illustrate spatial orientation of land and water bodies to each other. Considering their common purposes (showing direction, suggesting travel routes) they would not be of much use without clearly differentiating boundaries between the aforementioned regions. In attempting this demarcation it is certainly useful for mapmakers to color adjacent regions with different colors so as to most discernibly illustrate them as independent upon initial inspection. Therefore, a valid question would involve just how many colors are necessary to produce a map in which adjacent regions are differently colored.

This is the concept at the crux of the FCT, suggesting that all one-dimensional (or planar) maps, whether existing or imaginary, can be so colored with at most four colors. Oddly enough it has acquired a large following of mathematicians, rather than mapmakers, as its proof has progressed. This might be due to lack of encounters with existing land maps of such necessity, or the fact that there is no truly dire need to color maps with four colors or less. For whatever reason, the problem has been of only minor interest to those who actually color the items in question.

That is not to say that mathematicians did not partake in a great deal of map coloring themselves. It is rumored that FCT devotee George David Birkhoff spent his entire honeymoon coloring maps that he insisted his new wife draw for him [7]!

Other enthusiasts developed methods of coloring that more effectively portrayed colored regions and their boundaries, such as the edge and vertex method [f]. For the colored “map” (1) at left, each region A through E can be represented by a node or “vertex,” and the boundaries between them as “edges.” This way we can see the orientation of the regions and manipulate their colorings more easily.

Since, as Augustus De Morgan recognized, four regions at most may be in simultaneous contact with one another, we will need only worry about coloring vertices surrounded by at most four other vertices [8]. However, the numerous possible arrangements we must consider make this a very complicated task. So perhaps it is the mathematical complexity of the problem that suggests it may be better served with attention from the more mathematically inclined.

And this is what it got.

Colorful History

Proofs and contemplation of the FCT were attempted by a host of mathematicians throughout history. It was Francis Guthrie who first considered such a concept while coloring maps of England [9]; he later proposed to his brother Frederick (both students of the famous Augustus De Morgan)…

“..the greatest number of colours to be used in colouring a map so as to avoid identity of colour in lineally contiguous districts is four…”[7]

It was then Frederick who wrote De Morgan in 1852, asking him for any sort of clarification on the issue. De Morgan admitted that it seemed like a plausible assumption, yet could not figure out a way to prove it [8]. Slightly puzzled, he went to his friend Sir William Rowan Hamilton with the Guthrie brothers’ inquiry…

“…A student of mine asked me to day to give him a reason for a fact which I did not know was a fact – and do not yet. He says that if a figure be any how divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured – four colours are wanted, but not more… query cannot a necessity for five or more be invented…” [7]

Yet De Morgan’s letter seemed ineffective at arousing his friend’s curiosity; Sir Hamilton brusquely replied that he would “…not likely attempt [it] very soon.” [8]

Cayley Comes Calling

De Morgan died in 1871, and interest in the four coloring problem seemed to fade for a while. Luckily, another of his former students, Arthur Cayley, had learned of the problem and become very interested in how it might be proved. In 1878 he addressed the London Mathematical Society asking whether anyone had supplied a solution to Guthrie’s conjecture [2]. He learned that Charles Peirce’s had been the first attempt, although he proved quite unsuccessful in his endeavor [3]. Since no one else seemed to have considered it, responses were less than satisfactory to Cayley; he felt compelled to explore just what it was about this problem that eluded even brilliant minds. A while later he published a paper entitled “On the Coloring of Maps,” explaining his findings on the difficulty of the proof [1].

Kempe’s Attempt

One year after Cayley’s paper was published, and article appeared in the American Journal of Mathematics. A former student of Cayley’s, Alfred Bray Kempe, seemed to have found a solution to the four color problem! In “On the geographical problem of the four colours,” Kempe explained,

“… that a very small alteration in one part of a map may render it necessary to recolour it throughout…after a somewhat arduous search, I have succeeded… in hitting upon a weak point.” [7]

In his paper, Kempe endeavored to prove by induction that any planar map was four-colorable. To facilitate this aim, he established some basic but essential conventions; the first of these employing an extension of a formula by Euler. That is, if we let V represent the vertices of a region, F denote the region (or face) itself, and E correspond to its number of edges (boundaries), we have then V + F = E + 1. We can interpret this as saying that the number of vertices (or “meeting points”) and the number of regions added together are one more than the number of boundaries in a map.

Using this idea, Kempe showed that (for Rk = the number of regions with k boundaries),

5R1 + 4R2 + 3R3 + 2R4 + R5 - … = 0.

Because only the first five quantities are positive, Kempe argued that R1, R2, R3, R4, and R5 could not all be zero; we can combine this and Euler’s formula above to deduce that every map must have a region with fewer than six boundaries (proving de Morgan’s “only five neighbors” concept).

By this result, we are able to locate a region on any map that is bounded by five or less other regions. Kempe has us then cover this region with a “patch” of the same (but slightly larger) shape, and extend the boundaries of the surrounding regions so that they meet at a point on our patch. We have essentially now reduced that region to a single point, decreasing the number of countries on our map by one [7].

We repeat this “patching” process until there is just one region left with five or fewer other regions surrounding it, and we color it any of the four colors. Then we begin stripping our patches off in reverse order, coloring each re-revealed country with one of our available four colors. We repeat this process until the original map is restored, now colored with four colors so that no adjacent regions have the same color.

To ensure this result, Kempe had to consider what would happen when the last remaining un-patched region was surrounded by different numbers of regions. From before we know that this region may be bounded by up to five other regions, so we only need to consider five cases. Suppose we represent our regions with nodes or vertices, their boundaries with lines or edges, and denote the particular region in question as vertex “v.” When v is bounded only by one other node, we have two nodes to color (n = 2 case) and can definitely color them with four colors. When v is surrounded by two or three other nodes (n = 3 and n = 4) four colors still suffice. The trouble comes when n is surrounded by four or five other nodes (the n = 5 and n = 6 cases), for in such instances finding a color for v may be tricky.

So how do we know we will encounter these tricky situations? In his proof Kempe discusses certain arrangements of regions that we are bound to encounter in our coloring activities, later deemed “unavoidable sets.” Because any map that might jeopardize the four color theorem must at least contain a region with five or fewer surrounding regions (“only five neighbors” theorem), Kempe reasoned that the map must then contain region v with one of the following shapes:

We know what to do when we get a digon or triangle-shaped v, for there will always be a fourth color left with which to color it. However, if v is a square or pentagon shape, we run into trouble.

Kempe’s Chains

So to contend with these dilemmas, Kempe applies a rather clever trick. For the first case that gives us trouble, the “square” v (or n = 5), we assign the four nodes surrounding v to be colored red, green, yellow, and blue (see below). Since there is no color left for v, we must somehow change the color(s) of the surrounding nodes so that they only use three of the four colors without rendering the rest of the map impossible to four-color.

In order to do this, Kempe tells us to consider the relationships of the colored nodes to each other. In the case of the oppositely facing red and yellow nodes here, we could change the yellow node to red (or vice versa) as long as the two are not connected by an alternating chain of red and yellow nodes (left). This way, the four nodes surrounding v are colored with three colors, and there is a color left for v. In the example at left, we may now change v to yellow; we have successfully four-colored our map.

And if there is an alternating red and yellow chain connecting the original red and yellow nodes? Recall that our lines or edges represent the boundaries between two countries. Therefore, the lines cannot cross each other, as this would imply that one country can cross over into another (which would defeat the purpose of illustrating boundaries in the first place). Thus having such a chain connecting our red and yellow nodes would prevent the existence of a blue-green alternating chain connecting the blue and green nodes, as it would have to cross the red-yellow connective string. We could then change the green (or blue) node allowing v to be colored, thereby successfully four coloring the map (at left). Kempe uses a similar argument in proving the n = 6 case, where v is a pentagon surrounded by five other nodes colored with all four colors.

This technique later became known as Kempe’s Chain method, and afforded him great acclaim in the mathematical world. After the proof appeared in the American Journal of Mathematics in 1879, Kempe was made a Fellow of the Royal Society and later knighted for his significant contribution [4].

Heawood’s Hay day

Kempe’s celebrated proof, however, contained a small error. Eleven years after it had been widely accepted as true, Percy John Heawood (another map coloring enthusiast) discovered a counterexample map for which Kempe’s chain method failed. In his famous paper, “Map-Colouring Theorem,” Heawood explains somewhat apologetically that his “…aims are so far rather destructive than constructive, for it will be shown that there is a defect in the now apparently recognized proof…” [7] He went on to discuss the flaw in Kempe’s logic concerning the use of his chain method in the pentagonal n = 6 case, using the example at right (where r = red, g = green, b = blue, y = yellow, and v is the middle uncolored node).

You will notice that this particular coloring of the 25-region “map” results in the failure of Kempe’s chain method. The map actually is four colorable if it is colored differently! Heawood used this arrangement simply to expose the logical error in Kempe’s coloring technique. There are in fact more simplistic illustrations of such cases, involving fewer regions but where the chain method still fails; most notable are those presented by Alfred Errera and Charles-Jean-Gustave-Nicolas de la Vallée Poussin, who both discovered the error independent of Heawood [7].

Let us return again to Heawood, whose intentions in “Map-Colouring Theorem” were not entirely destructive. Although he was unable to reconstruct a four-color proof from Kempe’s failed one, he was able to correctly prove that any map on a sphere is five-colorable using Euler’s formula and a variation on Kempe’s chains [1]. Heawood also suggested appropriate numbers of colors for maps on a different three-dimensional surface, namely the torus. By an extension of Euler’s formula for a torus with n number of holes, we have

F – E + V = 2 – 2n,

from which Heawood derived the formula

C(n) = [ ½ (7 + √1 + 48n)]

(where C(n) represents the number colors needed to color a surface with n holes). Thus, for the torus above, we have n = 2 and

C(2) = [ ½ (7 + √1 + 48(2))]

= [ ½ (7 + √97)]

= [ 8.42 ]

 [ 8 ]. (so eight colors are needed for a two-holed torus)

This concept was set forth in “Map-Coloring Theorems” along with Heawood’s counter to Kempe’s proof [5]. However, even Heawood’s clever logic was not infallible; he overlooked a vital component in presenting his own proof. While he did correctly deduce the above formula for the number of colors needed to color an n-holed torus, he failed to show that there exists an n-holed torus requiring C(n) colors as determined by the formula. After this rather crucial discrepancy was exposed, his “theorem” became known instead as the Heawood Conjecture. It was not until 1968 – seventy-seven years after “Map-Colouring Theorems” was published – that Gerhard Ringel and Ted Youngs finally proved the hypothesis [7].

Before departing from Heawood’s work, it is interesting to note that a torus with zero holes (or, a sphere…) requires the following number of colors from his formula:

C(0) = [ ½ (7 + √1 + 48(0))]

= [ ½ (7 + 1)]

= [ ½ (8)]

= [ 4 ].

Although a pleasing result, this unfortunately does not prove the four color theorem. It turns out that Heawood’s formula only applies to n strictly greater than zero, as Ringel and Youngs found out [10].

So we leave Kempe and Heawood, having seen them both produce some remarkable results on map coloring (as well as committing a few mathematical faux pas along the way). We now turn our attention to how their work compared to that of other map-coloring mathematicians.

Connect the Colorists (er… dots)

Another of Cayley’s students, Peter Guthrie Tait, attempted to prove Guthrie’s conjecture around the same time that Kempe’s proof was refuted by Heawood. Tait is probably best known for his boasting that he had proved the theory, and not for the “proof” itself; one of his foundational “lemma[s] easily proven” on which he based his arguments turns out to be as challenging to prove as the four color theorem itself. However, it was Tait who introduced the idea of coloring the actual boundary lines of regions (instead of the regions themselves) as a way to solve the problem, and this method is still presently being considered [7].

Julius Petersen critiqued both Tait and Kempe’s work quite vocally, publishing his criticism in a popular new French mathematics periodical L’Intermédiaire des mathematiciens. He accused Kempe of “…only skim[ming] over the problem,” declaring that “…he committed his error just where the difficulties began.” Petersen went on to say that he was not entirely sure, but that “…if it came to a wager I would maintain that the theorem of the four colours is not correct.” [7]

Such comments might certainly have been instigated by the fact that Petersen was responsible for yet another graphical representation defying Kempe’s chain argument for the hexagonal shaped v (n = 6) case. Known as a Petersen Graph, this arrangement of eleven regions also resists Tait’s border coloring method and serves to counter his original proof using colored borders [11]. Perhaps it is understandable that Petersen, having come to this result and being aware of others like it, would be skeptical of the four color theory.

Troublesome Traits

If we may be allowed a short digression, consider once more where Kempe’s proof failed, specifically the examples that exposedits flaw. These surround his case when v is a hexagon, bordered by five other regions; for in this instance the Kempe chains become tangled and prevent us from four-coloring our map using his coloring method. Since this arrangement seems so difficult to deal with, a good question to ask might be whether it is possible to somehow represent the same situation of regions in another way that we can deal with.

German born mathematician Paul Wernicke was the first to address this question. He followed suit behind Kempe and Heawood; his initial work on the problem was unsuccessful, although he later produced some important results on unavoidable sets that would ultimately contribute to solving problem. Most notably, Wernicke added two more configurations to Kempe’s original unavoidable set, these being the cases where two connected pentagons are surrounded by six other regions, and where a connected pentagon and hexagon are surrounded by seven other regions [7].