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 fourcolor conjecture was Alfred Bray Kempe. Kempe (18491922) 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 fourcolor 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 fourcolor 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 3valent 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 4sided 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 dcolored 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 db 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 bcolored 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 ccolored 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 4color problem.
After correctly arguing about how to handle a 4sided region (4gon) surrounded by regions that used all four colors, Kempe tried to extend his argument to the case of a 5sided region (5gon) surrounded by regions that used all four colors. Here his argument had a mistake. The error in Kempe's proof of the fourcolor conjecture went unnoticed for some time. His work appeared in print 1879. The mistake was noted by Percy John Heawood (18611955) 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 mapcoloring 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 fourcolor 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 graphcoloring 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 fourcolor 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 easytostate problem from over 150 years ago are still being explored. These questions involve coloring graphs, embedding graphs on surfaces, and applications of these ideas.

Introduction

Basic ideas

Face colorings

Vertex colorings

Some history

References
Welcome to the
Feature Column!
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .
Feature Column at a glance