Tait's Reformulation of the Four Color Theorem

The Two Coloring Problems

A map-coloring problem assigns colors to regions so that regions sharing a boundary edge receive different colors. In graph language, the regions become vertices of the plane dual, and neighboring regions become adjacent vertices. Tait’s reformulation replaces this vertex-coloring problem with an edge-coloring problem on a different plane graph. The equivalence is useful because it turns a four-color question into a precise question about cubic graphs.

All graphs in this tutorial are finite. A plane graph is a graph together with a particular embedding in the plane, with edges meeting only at common endpoints; a planar graph is one that admits such an embedding. A graph is cubic if every vertex has degree \(3\), and it is bridgeless if deleting any one edge does not increase the number of connected components. A proper edge coloring assigns colors to edges so that edges sharing an endpoint have different colors.

We will prove the equivalence. In the proof, it is convenient to represent the four colors by the elements of the group \(\mathbb{Z}_2\times\mathbb{Z}_2\). Write these as \(0,a,b,c\), where \(a+b=c\), \(a+c=b\), \(b+c=a\), and \(x+x=0\) for every element \(x\). Thus the sum of any two distinct nonzero elements is the third nonzero element.

The plane dual \(G^*\) has one vertex for each face of a connected plane graph \(G\), and an edge crossing each edge of \(G\), joining the vertices for the two faces on its sides. We use two standard dual facts: a dual edge is a loop exactly when its corresponding primal edge is a bridge, and a plane triangulation (a connected plane graph with every face bounded by a triangle) has a cubic dual. The first fact explains why bridgelessness matters; the second explains why triangulations enter the other direction of the proof.

From Four Colors to Three Edge Colors

Assume the Four Color Theorem. Let \(H\) be a connected bridgeless cubic plane graph. Its dual \(H^*\) has no loops, because \(H\) has no bridges. Apply the Four Color Theorem to \(H^*\), coloring its vertices with elements of \(\mathbb{Z}_2\times\mathbb{Z}_2\). For each edge \(e\) of \(H\), let \(F_1,F_2\) be the faces of \(H\) on its two sides, and give \(e\) the label equal to the sum of the colors of the corresponding dual vertices.

We check that this is a proper three-edge-coloring. First, the faces around any cubic vertex \(v\) of \(H\) are distinct. If two of the three sectors at \(v\) belonged to the same face, two consecutive sectors in the cyclic order around \(v\) would belong to the same face. The edge separating those sectors would then have the same face on both sides, so it would be a bridge, contrary to the hypothesis. Thus the three faces around \(v\) correspond to three distinct, pairwise adjacent vertices of \(H^*\). Their colors are distinct. The three edges incident with \(v\) receive the pairwise sums of these three colors. Those sums are precisely the three distinct nonzero elements \(a,b,c\). Hence the edge labels are proper at \(v\), and this holds at every vertex.

If \(H\) is disconnected, apply the same argument to each component. Each component is still cubic and bridgeless, and the component colorings together give a Tait coloring of \(H\).

From Three Edge Colors to Four Colors

Now assume every bridgeless cubic plane graph has a Tait coloring. We first handle a connected plane triangulation \(T\). Its dual \(H=T^*\) is cubic. It is bridgeless: a bridge in \(H\) would correspond under duality to a loop in \(T\), but a triangulation has no loops. Give the edges of \(H\) a Tait coloring with labels \(a,b,c\). Transfer each edge label to the corresponding edge of \(T\).

We next show that these edge labels determine vertex colors on \(T\). Around each triangular face of \(T\), the three boundary edges correspond to the three edges incident with one vertex of \(H\). Their labels are therefore \(a,b,c\), in some order, and their sum is \(a+b+c=0\).

In fact, the sum of the edge labels around every closed walk in \(T\) is \(0\). For a simple cycle, sum the zero-sum equations for all triangular faces inside it. Every interior edge occurs twice and cancels, since \(x+x=0\); the uncancelled edges are exactly the cycle edges. A closed walk with a repeated vertex splits at that vertex into shorter closed walks. Repeatedly splitting reduces it to simple cycles and immediate reversals; a reversal traverses one edge twice, whose label sum is also zero. This proves the claim for every closed walk.

Fix a root vertex \(r\) of \(T\), assign it color \(0\), and define the color of any vertex \(v\) as the sum of the labels along a path from \(r\) to \(v\). This is well-defined: two such paths, one followed by the reverse of the other, form a closed walk, whose label sum is zero. For an edge \(uv\), a path from \(r\) to \(u\), followed by \(uv\) and the reverse of a path from \(r\) to \(v\), is a closed walk. Its label sum is zero, so the colors of \(u\) and \(v\) differ by the nonzero label on \(uv\). Thus the vertex coloring is proper and uses at most four colors.

To pass from triangulations to all planar graphs, use the standard triangulation-extension fact: a finite simple plane graph on at least three vertices can be enlarged, without adding vertices, to a plane triangulation by adding edges. Coloring the enlarged graph and then deleting the added edges gives a coloring of the original graph. Components can be treated separately; components with one or two vertices are directly colorable with at most two colors. A plane map is colored by applying this graph statement to its dual. This proves the Four Color Theorem from the Tait-coloring assertion.

What the Equivalence Does—and Does Not—Say

The result is an equivalence of statements, not a shortcut that proves the Four Color Theorem by itself. If one can prove that every bridgeless cubic plane graph has a Tait coloring, the construction above gives four colors for every planar map; conversely, a four-color theorem supplies a Tait coloring for every bridgeless cubic plane graph. The two problems have the same mathematical force.

The hypotheses are essential to the formulation. Cubic means there are exactly three incident edges to color at each vertex, so the local condition is precisely that those three edges receive the three different labels. Bridgelessness ensures that the dual has no loops and that the three faces around each cubic vertex are distinct. One must not apply the proved correspondence to an arbitrary cubic plane graph without checking the bridge condition.

Common mistake: using ordinary numerical differences as edge colors. In the tetrahedron example, assigning the numbers \(0,1,2,3\) and taking ordinary absolute differences gives labels \(12=1,\ 23=1,\ 13=2\). At the dual vertex for face \(123\), the labels are \(1,1,2\), which are not a proper edge coloring. The correction is to use the group \(\mathbb{Z}_2\times\mathbb{Z}_2\): the colors \(0,a,b\) give pair sums \(a,a+b,b\), namely \(a,c,b\), all distinct. The group operation, not ordinary subtraction of integers, is what makes the conversion work.