Feature Column from the AMS

Colorful Mathematics: Part I

5. Some history

Having noticed that it appears that any plane map can be colored with four or fewer colors, attempts were made to prove this result. One person who responded to the challenge of trying to prove the four-color conjecture was Alfred Bray Kempe. Kempe (1849-1922) had studied with the distinguished British mathematician Arthur Cayley when he was a student at Cambridge University. Although Kempe earned his living as a lawyer (barrister), he made significant contributions to mathematics in several different areas. He presented an ingenious argument in attempting to prove the four-color conjecture. His ideas have proved to be very important to the future of coloring problems even though the way he used his ideas in attempting to prove the four-color problem were not fully correct.

Kempe's argument was so convincing that it was quite a few years before Percy Heawood noticed that it was incorrect. Kempe's approach reduced the problem to coloring the faces of 3-valent plane maps. The key idea of the proof involved is what are known today as Kempe chains. Suppose that one is coloring a map and one has a 4-sided region R which has faces which have been already colored with the four colors available. Kempe wanted to be able to recolor the map so that the coloring rule was met but that R could be colored. Suppose the colors (a, b, c, and d) around the region R are as represented in the diagram below:

Now consider all the regions that are colored b and d. Either there is a chain of b- and d-colored regions that connect region 4 and region 2, or no such chain exists. If no such chain exists, we can interchange the colors of region 4 and those regions to which it is connected in the d-b color chain, leaving region 2 colored by b. This color interchange colors region 4 with b. Now, region 4 and region 2 are colored b and we have the neighbors of R using only three colors, so that we can use the 4th color (b) for region R. In the case that there is a chain of d- and b-colored faces from region 2 to region 4, we can be assured, by a simple topological result following from the Jordan Curve Theorem, that there can be no chain of a- and c-colored faces from region 1 to region 3. Thus, arguing as we did above, we can free up a color to use on region R. Kempe chains can be adapted to apply in the vertex coloring version of the 4-color problem.

After correctly arguing about how to handle a 4-sided region (4-gon) surrounded by regions that used all four colors, Kempe tried to extend his argument to the case of a 5-sided region (5-gon) surrounded by regions that used all four colors. Here his argument had a mistake. The error in Kempe's proof of the four-color conjecture went unnoticed for some time. His work appeared in print 1879. The mistake was noted by Percy John Heawood (1861-1955) in 1890.

However, something good came out of Kempe's work. First, Heawood provided a proof that five colors were always sufficient to color the regions of any plane map. Second, he went beyond questions raised in Kempe's work by asking map-coloring questions about very general surfaces. Heawood showed, in a more recent formulation, that if G is a graph which has been drawn (embedded) on a surface which has genus g > 0 then:

The genus of a surface with positive genus g can be thought of as a sphere with g handles attached. You can think of a surface with genus 1 as a donut (torus with 1 hole) and a surface with genus 2 as a donut with two holes. Eventually, in 1968 G. Ringel and J.W.T. Youngs showed that one can replace the inequality above with an equality. The issue of the chromatic number for maps on surfaces with negative genus (unorientable surfaces) has also been accomplished; all this, before the four-color problem, which emerges from the formula above when g is set to be zero, was settled! Thus, Heawood formulated ideas that have kept people interested in coloring problems busy to the present day. Not only did he make important contributions to graph-coloring problems, but he is famous for his devotion to overseeing repairs to Durham Castle in England, which had, due to neglect, developed structural problems. Heawood helped to ensure that it was restored to its former glory.

In a later column I will treat some of the more recent directions of research in coloring problems, continue the history of how the four-color problem was resolved, and describe some of the exotic coloring problems that have been considered and are leading in many exciting new directions. Developments initiated by an easy-to-state problem from over 150 years ago are still being explored. These questions involve coloring graphs, embedding graphs on surfaces, and applications of these ideas.