Colorful Mathematics: Part II

4. The Hamilton connection

A lovely and curiously simple-to-prove result connects the face-coloring version of the four-color problem to the theory of Hamiltonian circuits.

Theorem:

If a plane graph G has a Hamiltonian circuit, then the faces of G can be colored with 4 (or fewer) colors.

Proof:

Let G be drawn in the plane and let C be a Hamiltonian circuit of G. By the Jordan Curve Theorem points not on C are either interior to C or exterior to C. Thus, any additional edges must lie in the interior of C or in its exterior. This means that we can alternately color the regions in the interior of C by switching colors each time we move across an "interior diagonal" edge. Similarly we can color the edges in the exterior of C with two colors, different from the ones used in the interior of C.

By way of example, in the diagram below a Hamiltonian circuit is shown highlighted in thick black lines. The regions inside the Hamiltonian circuit are colored with yellow and green, while the regions outside the Hamiltonian circuit are colored in blue and red. The edges of the original graph that are not part of the Hamiltonian circuit are shown with thin black lines.
 

 

Any plane graph, whether it is 3-valent or not, that has a Hamiltonian circuit can be so colored with 4 colors . Unfortunately, there are infinitely many graphs that have no Hamiltonian circuit so this approach to trying to prove the four-color theorem did not prove fruitful. However, there is an interesting story here.

Early in the history of the four-color conjecture, in its face-coloring version, it was shown that it was sufficient to prove the conjecture for a special class of plane maps. These are the plane maps which represent 3-dimensional convex polyhedra which are 3-valent. A purported proof was published that indicated that all such polyhedra had Hamiltonian circuits. However, many people were skeptical of the proof but could not explicitly point to an error. On the other hand, no one knew of an example of a planar 3-valent, 3-connected graph (which are the conditions of a beautiful theorem by Steinitz to guarantee that a graph can be realized by a 3-dimensional convex polyhedron) which lacked a Hamiltonian circuit (a 3-connected graph is one with the property that given any two vertices v and w of the graph, there are at least three paths from v to w which have only v and w in common).
 

In 1946, William Tutte (1917-2002, pictured above) produced an example (below) of a planar 3-valent 3-connected graph without a Hamiltonian circuit which had 46 vertices. Tutte was born in Britain but spent a lot of his professional career teaching at the University of Waterloo in Canada. He made many deep contributions to graph theory.
 

Somewhat later, examples of this kind with 38 vertices were found.

Eventually it was shown that any plane 3-valent 3-connected graph with 36 or fewer vertices has a Hamiltonian circuit. Although this line of investigation turned out to be a dead-end with respect to finding a simple proof of the four-color problem, the progress both in theorems and proof techniques for geometrical ideas in graph theory has been dramatic. Results concerning Hamiltonian circuits are still being pursued vigorously, and relations between issues involving Hamiltonian circuits and coloring problems are still being pursued.

If a graph is 3-valent (plane or not) and has a Hamiltonian circuit, one can also easily see why the edges of the graph can be colored with 3 colors. This is because in a 3-valent graph the number of vertices must be even (because 3V = 2E). Thus, one can alternately color the edges of the Hamiltonian circuit with two colors. The remaining edges can be colored with a third color.

In the next column, we will continue our discussion of coloring problems and their applications.

1. Introduction
2. Insights into coloring planar graphs
3. Edge-colorings
4. The Hamilton connection
5. References