Tait Coloring

Diagrams and text by Philip Rideout, 23 May 2020.

Every diagram on this page is an SVG. To see a larger picture, right-click any image and open it in a new tab. You can also re-use these images, they are released under CC BY 4.0.

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.

Every planar 3-connected graph has a planar drawing such that every vertex which is not on the outer cycle is the barycenter of its neighbors.

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:

Every planar graph is 4-colorable if and only if every planar bridgeless cubic graph is 3-edge-colorable.

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

  1. Removing edges from a vertex-colored graph does not change the validity of its coloring.
  2. All planar graphs have triangulations.
  3. Therefore, if all triangulated graphs are 4-colorable, then all planar graphs are 4-colorable.

This allows us to transform our hypothesis to:

Every triangulated graph is 4-colorable if and only if every planar bridgeless cubic graph is 3-edge-colorable.

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

  1. The vertex coloring of a graph is equivalent to the face coloring of its dual.
  2. The dual of any triangulated graph is a bridgeless planar cubic graph.

Thus, it is sufficient to prove the following.

Every planar bridgeless cubic graph is 4-face-colorable if and only if every planar bridgeless cubic graph is 3-edge-colorable.

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:

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.

Here’s the result:

You can also think about Tait Coloring in terms of binary numbers. Each of the original four colors can be represented by a two-digit binary number, in which case the edge color is equivalent to the XOR operation applied to adjacent faces.

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à!