Feature Column from the AMS

Colorful Mathematics: Part III

2. New problems from old ones

Mathematicians are trained to take a given problem and specialize it and generalize it in the hope that either new insights or new mathematical methods will emerge. Furthermore, if a particular mathematical statement can be proven with a new technique, mathematicians are trained to try to look for new problems which might also be proven with this technique. In part this is the way that mathematics grows. Mathematicians are also inspired by problems that arise outside of mathematics.

The four-color problem was to try to prove that the faces of any plane map could be colored with four or fewer colors. In order to get insight, one might ask the following "specialized" questions:

a. What plane maps can be face-colored with exactly one color?

b. What plane maps can be face-colored with exactly two colors?

c. What plane maps can be face-colored with exactly three colors?

d. What plane maps can be face-colored with exactly four colors?

(A phrase such as "face-colored with exactly three colors" means that the map can be colored with three, but not fewer, colors.)

Below is an example of a graph for which the associated "map" can be face-colored with exactly one color.

A graph whose associated map can be face-colored with one color

Based on the example, can you determine what kind of plane maps can be colored with exactly one color?

It turns out there is a very appealing theorem which answers the question of when a plane graph can be colored with exactly two colors.

Theorem A:

A plane graph can be face-colored with exactly two colors if and only if the valence of all the vertices of the graph is even.

An example of an even-valent graph and a two-coloring of its faces is shown below. Note that not all of the faces are 3-gons (triangles).

Map which has been face-colored with two colors

An interesting corollary of this theorem is that a map formed by intersecting straight lines in the plane or by circles drawn in the plane can be colored with two colors.

Moving on to the question of coloring the faces of a plane graph with three colors, we have the following very appealing theorem:

Theorem B:

The faces of a 3-valent plane graph can be colored with three colors if and only if all the faces have an even number of sides.

#-valent map which has been three-face-colored

Theorems A and B, in addition to the simplicity of their statements, are interesting for another reason: they can be formulated using other ideas that have proved very fruitful in graph theory.

When Euler first invented the notion of a graph in 1736, it was in connection with his solution of the Königsburg bridge problem. The problem was whether it was possible to design a walking tour which crossed over each bridge of the city once and only once, returning to one's starting point. Today, a tour of the edges of a connected graph (i.e. one consisting of only one piece) which starts and ends at the same vertex and traverses each edge once and only once is known as an Eulerian circuit. Today we would summarize what Euler set in motion with the theorem:

Theorem:

A connected graph has an Eulerian circuit if and only if every vertex is even-valent.

Hence, we can restate the 2-color theorem for faces of a plane graph:

Theorem A*:

A plane graph can be face-colored with two colors if and only if the graph has an Eulerian circuit.

Similarly, in thinking about Theorem B, it can be reformulated using the idea of bipartite graph. A bipartite graph is one for which the vertices can be divided into two sets X and Y so that the edges of the graph have one end in X and one end in Y. It is not difficult to see that bipartite graphs have the property that any circuits in such graphs have even length. Thus,

Theorem B*

The faces of a 3-valent plane graph can be three-colored if and only if the graph is bipartite.

On the one hand Theorems A* and B* really say no more than Theorems A and B. However, because of the connotations of the new terminology of Theorems A* and B* they suggest questions and ideas that might not have been investigated without the reformulations.

In discussing how new results in mathematics evolve, let us now look at the vertex-coloring versions of these face-coloring problems for plane graphs. Using the fact that one can associate a "dual graph" with a plane graph one can also formulate questions about coloring the vertices of a graph with exactly one, exactly two, exactly three, or exactly four colors. For example, can you discover for yourself the statement of a theorem concerning when the vertices of a graph can be colored with exactly one color? Here are some other results that come from the dual results of those we have already discussed:

Theorem Dual A:

The vertices of a plane graph can be colored with two colors if and only if the graph is bipartite.

3-valent plane graph whose vertices have been two-colored

Note that for plane graphs, the fact that bipartite graphs have only circuits of even length is reflected in the fact that each face of the graph has an even number of sides.

Here is the dual theorem to B:

Theorem Dual B:

A plane graph in which each face is a triangle can be 3-vertex colored if and only if every vertex is even-valent.

Here is an example which illustrates this result:

Plane graph with triangular faces whose vertices have been three-colored

The four-color problem is a problem about plane graphs, so I have formulated the problems above in terms of plane graphs. You may want to see which of the theorems about vertex-colorings apply to graphs which are not planar. Even for plane graphs, determining precisely which such graphs can be vertex-colored with exactly 3 colors is exceedingly complex. (Our theorem above deals not with general plane graphs, but only with graphs whose faces are triangles.) On the negative side it is known that the following decision problem is NP-complete: Can a given plane graph G be 3-colored? This means that it is unlikely that a "fast algorithm" will ever be found which for a given graph answers the question of whether the graph has a vertex three-coloring. On the positive side there are some lovely results about three colorings. Here is an especially nifty result due to H. Grötzsch (1959).

Theorem (Grötzsch):

Any planar graph whose shortest circuit has length at least four is 3-colorable.

Not only is this true, but if one has a circuit of length 3 or 5 in such a graph, which one colors using three colors, then this initial vertex-coloring of a circuit can be extended to a 3-coloring of the whole graph. Grötzsch's Theorem has been proven in a variety of ways quite different from Grötzsch's original proof, and has been extended in many ways. There also has been a lively interest in the question of how to "complete" a "partial" coloring of a graph.