Tait Coloring

Diagrams and text by Philip Rideout, 23 May 2020.

In the late 19th century, the distinguished University of Edinburgh professor Peter Tait published his own proof of the Four Color Theorem. Much like other attempts that have been made over the years, Tait’s proof contained an oversight.

However Tait’s efforts resulted in a legitimate and very important contribution to graph theory. He was able to morph the four color problem into a slightly different problem. Before describing this in detail, let’s review the Four Color Theorem. Consider an example of a map and its representation as a graph:

We would like to color the regions in the figure on the left (or vertices in the figure on the right), such that no two adjacent regions (or vertices) receive the same color. In general, what is the minimum number of required colors? The answer is four, but this was not proven until the late 20th century. And even then, only with help from software.

The figure on the right is the dual of the figure on the left. Duals are transformations that work like mirrors: the dual of the dual is the thing itself. For planar graphs and polyhedra, the dual is defined by replacing every face with a vertex in its interior. (Technically the graph is the weak dual of the map since it does not include a vertex for the unbounded external face.)

One piece of trivia: if you find the dual of any of the five Platonic solids, the result is another Platonic solid. This beautiful finding was first documented by Johannes Kepler in 1619.

Let’s return to 19th century Scotland. Tait successfully proved that the following two statements are equivalent:

1. The vertices of every planar graph are 4-colorable.
2. The edges of every planar bridgeless cubic graph are 3-colorable.

That first statement is simply a formal way of defining the Four Color Theorem. Graphs that are planar can be drawn such that their edges never cross.

The second statement applies to a more constrained class of graphs, so it is surprising that it is somehow equivalent to the Four Color Theorem. It only applies to cubic graphs (sometimes known as trivalent graphs), which are graphs that have exactly 3 edges adjacent to every vertex. Moreover they must be bridgeless, which means that there are no “bare” edges as seen in the following figure. The edge in the middle has the same face on either side (namely, the infinite outside face) so this graph is not bridgeless.

Any planar graph can be transformed into a planar bridgeless cubic graph by applying triangulation, then by taking the dual. Let’s examine this process in detail.

Step 1: Triangulation

Planar graphs can be triangulated by adding edges into each face that has more than 3 sides. Stated another way: create a graph that includes the maximal set of non-crossing edges, such that the graph is maximally planar. One way of triangulating the example at the top of this post is shown below. New edges are shown in blue.

Note that our example graph is getting a bit unwieldy due to the arcs from the triangulation of the infinite outer face. If we were to omit these edges, the graph would be considered a near triangulation.

We can obtain a nicer drawing by leveraging the following discovery of Bill Tutte, a World War II codebreaker.

Stated another way: to make a drawing without crossings, take any face in the graph, stretch it out and pin it down, then allow all other vertices to move around as though they were connected with springs. Amazingly, this always produces a crossing-free drawing, provided that the graph is actually planar.

Here’s the same triangulated graph after applying Tutte’s spring trick.

Keep in mind this is the same graph as the earlier one: the vertex positions have moved, but the connectivity is the same. Thus, it is isomorphic to the original.

Step 2: Obtaining the dual

Since every face in a triangulated graph has 3 sides, its dual is obviously cubic. The below figure depicts the dual of our triangulated graph. The original graph is called the primal graph. The grey polygons in the background represent the primal faces.

The outside vertex with emanating arcs corresponds to the infinite outer face in the primal graph.

Step 3: Transforming the problem statement

Let’s return to the original problem. We wish to prove the following:

We can rephrase this a little. Consider the following logic:

This allows us to transform our hypothesis to:

Let’s transform it again by applying the following two lemmas:

Thus, it is sufficient to prove the following.

Let’s refer to the first part of the hypothesis as 4FCS (four face color statement) and the second part as 3ECS (three edge color statement). One way of proving this equivalence is to show that both of the following are true:

• If 4FCS is true, then 3ECS is true.
• If 3ECS is true, then 4FCS is true.

Step 4. Showing that 4FCS implies 3ECS

Let’s assume that we have a proper 4-coloring of a triangulated graph (left) and therefore have a proper 4-coloring for the faces of its dual (right).

Next we need to construct a 3-edge coloring. Tait figured out a way to do so.

• Make the edge red when it is between red / yellow faces, or between blue / green faces.
• Make the edge green when it is between red / blue faces, or between yellow / green faces.
• Make the edge blue when it is between red / green faces, or between blue / yellow faces.

Here’s the result:

Tait proved that applying this procedure always yields a proper edge coloring, meaning that no two edges emanating from a single vertex share the same color.

Step 4. Showing that 3ECS implies 4FCS

In order to establish a bijection between the two theorems, we now need to show the converse of the implication that was demonstrated in the previous section. In other words, if we assume that we already have a proper 3-edge coloring of a triangulated graph, how can we obtain a proper 4-coloring for the faces? Tait figured this out too.

The first step is to pick two colors (A and B) and produce two new graphs: one that has A-colored edges removed, and one that has B-colored edges removed. These are shown below.

Next, examine the cycles (fenced-in areas) in the previous graphs. For each face in the graph, count how many fences it lives in. If the face is enclosed in an odd number of fences, apply a color to the face. Performing this operation with the two above graphs results in first two graphs below.

For the last step, superimpose the two graphs. This yields the graph on the far right, which has a proper 4-coloring. Et voilà!