From Edge Labels to Face Colors
A proper three-edge-coloring of a cubic plane graph assigns three different colors to the edges incident with each vertex. Tait’s reformulation links such an edge-coloring to a coloring of the faces: cross an edge, and change the face color by an amount determined by that edge’s color. The essential issue is consistency. A face may be reached from a chosen starting face by many paths in the dual graph, so the accumulated change must be the same along every path.
We use finite loopless plane graphs; parallel edges are allowed. A graph is cubic if every vertex has degree \(3\), and bridgeless if deleting any edge leaves its connected component connected. A proper three-edge-coloring assigns one of three colors to each edge so that edges sharing a vertex receive different colors. The plane dual \(G^*\) has one vertex for each face of \(G\), and one dual edge crossing each primal edge, joining the faces on its two sides. The dual may have parallel edges. Since \(G\) is bridgeless, its dual has no loops: a bridge has the same face on both sides, whereas a non-bridge does not.
The arithmetic is especially suited to this construction: every element added to itself gives \(0\), and \(a+b=c\), \(a+c=b\), and \(b+c=a\). In particular, \(a+b+c=0\). At each vertex of a properly three-edge-colored cubic graph, all three labels occur, so their sum is zero. We will use that local fact to prove the global path-independence claim.
Why the Accumulated Label Is Path-Independent
A dual walk records a sequence of faces, crossing a primal edge at each step. Its accumulated label is the group sum of the labels of the crossed primal edges, counted with their multiplicities. Repeated crossings matter: in this group, crossing the same edge twice contributes its label twice, hence contributes \(0\) in total.
Proof. Fix a closed dual walk and let \(D\) be the set of primal edges whose dual edges are traversed an odd number of times. At every dual vertex, the number of incidences from the walk is even, so \(D\), viewed as a set of dual edges, has even degree at every dual vertex. The label sum along the walk is exactly the sum of the labels of the edges in \(D\), because even-multiplicity contributions cancel.
We first show that \(D\), regarded as a set of primal edges, is a cut. Work with parity modulo \(2\), so sets of edges are added by symmetric difference. Let \(C\) be any cycle of the primal graph. Its embedded curve separates the plane into an inside and an outside. The dual edges crossing \(C\) are precisely the edges between the dual vertices for faces inside and those for faces outside. Since \(D\) has even degree at every dual vertex, it crosses any such partition an even number of times: summing the degrees of the dual vertices on one side counts internal edges twice and crossing edges once. Therefore \(|D\cap E(C)|\) is even.
For completeness, this parity property implies that \(D\) is a cut. In each connected component of the primal graph choose a spanning tree and a root. For each vertex \(v\), let \(s(v)\in\mathbb Z_2\) be the parity of the number of edges of \(D\) on the tree path from the root to \(v\). Every tree edge \(uv\) belongs to \(D\) exactly when \(s(u)\ne s(v)\). For a non-tree edge \(uv\), that edge together with the unique tree path from \(u\) to \(v\) forms a cycle. The cycle has an even number of edges in \(D\), so \(uv\in D\) exactly when \(s(u)\ne s(v)\) as well. Thus \(D\) consists precisely of the edges with one endpoint in \(S=\{v:s(v)=1\}\) and the other outside \(S\): it is the cut \(\delta(S)\).
Now sum the labels on the edges of \(\delta(S)\). Sum instead, for every vertex in \(S\), the labels of its three incident edges. Each edge internal to \(S\) is counted twice and contributes \(0\); each edge of \(\delta(S)\) is counted once. At each vertex the three labels are \(a,b,c\), whose sum is \(0\). Consequently the sum of the labels on \(\delta(S)=D\) is \(0\). This is the sum along the original closed dual walk, proving the lemma. \(\square\)
The dual is connected: a curve between points in any two faces can be chosen to avoid vertices and to cross edges finitely many times, giving a dual walk. So we can choose a base face and reach every face by a dual path.
Proof. Choose a base face \(F_0\) and assign it the group color \(0\). For any other face \(F\), choose a dual path from \(F_0\) to \(F\) and assign \(F\) the sum of the edge labels crossed along that path. To see that this is well-defined, take two paths from \(F_0\) to \(F\). Following the first and then the second in reverse gives a closed dual walk. By the lemma its label sum is \(0\), so the two path sums agree.
If faces \(F\) and \(H\) share an edge labeled \(x\), a path to \(H\) can be formed by taking a path to \(F\) and then crossing that edge. Their assigned colors therefore differ by \(x\). Since \(x\) is one of \(a,b,c\), it is nonzero, and the two face colors are distinct. This holds for each pair of faces sharing an edge, so the coloring is proper and uses only the four elements of the group. \(\square\)
Worked Constructions
Worked Example: The Tetrahedral Plane Graph
Take \(G\) with vertex set \(\{1,2,3,4\}\), edge set \(\{12,13,14,23,24,34\}\), and the plane embedding whose faces are \(F_{123},F_{124},F_{134},F_{234}\). Color edges \(12,34\) by \(a\), edges \(13,24\) by \(b\), and edges \(14,23\) by \(c\). At each vertex the three incident edges have three different colors, so this is a proper three-edge-coloring.
Set the color of \(F_{123}\) to \(0\). Face \(F_{124}\) shares edge \(12\), labeled \(a\), with \(F_{123}\), so its color is \(0+a=a\). Face \(F_{134}\) shares edge \(13\), labeled \(b\), with \(F_{123}\), so its color is \(0+b=b\). Face \(F_{234}\) shares edge \(23\), labeled \(c\), with \(F_{123}\), so its color is \(0+c=c\).
Check the other shared edges too: \(F_{124}\) and \(F_{134}\) share \(14\), labeled \(c\), and \(a+b=c\). Faces \(F_{124}\) and \(F_{234}\) share \(24\), labeled \(b\), and \(a+c=b\). Faces \(F_{134}\) and \(F_{234}\) share \(34\), labeled \(a\), and \(b+c=a\). Thus every adjacent pair has different colors, as the construction requires.
Worked Example: Two Routes Around a Dual Cycle
Use the same tetrahedral graph and labels. Consider the dual walk \(F_{123},F_{124},F_{134},F_{123}\). It crosses edges \(12,14,13\), whose labels are respectively \(a,c,b\). The sum is \(a+c+b\). Since \(a+c=b\), this equals \(b+b=0\). So this closed walk makes no net change.
There is also a direct check using the face colors just computed: \(F_{123}\) has color \(0\), \(F_{124}\) has color \(a\), \(F_{134}\) has color \(b\), and returning to \(F_{123}\) changes the color by \(b\). The total change along the route is \(a+c+b=0\), so the final color is again \(0\). The calculation illustrates why adding labels, rather than assigning an unrelated color at each step, gives consistent results.
Worked Example: Coloring the Faces of a Cube
Let the vertices be \(u_0,u_1,u_2,u_3,v_0,v_1,v_2,v_3\), with indices around each square taken cyclically. The edges are \(u_0u_1,u_1u_2,u_2u_3,u_3u_0\), \(v_0v_1,v_1v_2,v_2v_3,v_3v_0\), and the four edges \(u_iv_i\) for \(0\le i\le3\). This is the usual plane drawing of a cube: the \(u\)-vertices form the outer square and the \(v\)-vertices the inner square.
Color \(u_0u_1,u_2u_3,v_0v_1,v_2v_3\) by \(a\); color \(u_1u_2,u_3u_0,v_1v_2,v_3v_0\) by \(b\); and color every \(u_iv_i\) by \(c\). At each vertex, its two square edges have labels \(a,b\), and its remaining edge has label \(c\), so the edge-coloring is proper.
Name the outer and inner faces \(O\) and \(I\). Let \(S_i\) be the side face bounded by \(u_iu_{i+1}\), \(v_iv_{i+1}\), and the two corresponding edges \(u_iv_i,u_{i+1}v_{i+1}\), with indices modulo \(4\). Set the color of \(O\) to \(0\). Crossing outer edge \(u_0u_1\), labeled \(a\), gives \(S_0\) color \(a\). Crossing \(u_1u_2\), labeled \(b\), gives \(S_1\) color \(b\); crossing \(u_2u_3\), labeled \(a\), gives \(S_2\) color \(a\); crossing \(u_3u_0\), labeled \(b\), gives \(S_3\) color \(b\).
The inner face has color \(0\): from \(S_0\), crossing \(v_0v_1\), labeled \(a\), gives \(a+a=0\). Check the remaining side adjacencies: \(S_0,S_1\) differ by \(a+b=c\), matching their shared spoke \(u_1v_1\); \(S_1,S_2\) differ by \(b+a=c\); \(S_2,S_3\) differ by \(a+b=c\); and \(S_3,S_0\) differ by \(b+a=c\). Each side face also differs from \(O\) across its outer edge and from \(I\) across its inner edge, whose labels are nonzero. Hence all adjacent faces have different colors.
Why the Hypotheses Matter
The construction uses the edge labels as changes between face colors. A proper three-edge-coloring makes the three incident labels at each cubic vertex sum to zero; the cut argument then forces every closed dual route to have total change zero. These are separate roles: the local vertex condition gives the zero-sum identity, while planarity relates closed dual walks to primal cuts.
Bridgelessness matters for properness of the face coloring. If an edge is a bridge, the same face lies on both sides of it, so its dual edge is a loop. Crossing that edge would require the face to differ from itself by a nonzero label, which is impossible. A loopless dual is therefore essential to the conclusion that every crossed edge joins two distinct faces.
Common mistake: treating the edge colors as ordinary integers. Suppose one replaces the three labels by \(1,2,3\) and adds them modulo \(4\). At a cubic vertex, \(1+2+3=6\), which is \(2\) modulo \(4\), not \(0\). This does not give the cancellation needed in the cut argument. With the group labels, \(a+b+c=(1,0)+(0,1)+(1,1)=(0,0)=0\), with each coordinate calculated modulo \(2\). The group operation is part of the proof, not merely a choice of notation.
This result is a conditional conversion: whenever a bridgeless cubic plane graph has a proper three-edge-coloring, the construction produces a proper four-coloring of its faces. It does not assume that every such graph has the required edge-coloring. The value of the conversion is that it makes the relationship between Tait edge-colors and face-colors explicit and proves that the resulting face colors are globally consistent.
Check Your Understanding
Use group addition modulo \(2\) in each coordinate when carrying out the calculations.
- Why does a properly three-edge-colored cubic vertex have incident labels whose sum is \(0\)?
- For the tetrahedral example, compute the color of \(F_{234}\) along the route \(F_{123},F_{124},F_{234}\).
- In the proof of the lemma, why does an even-degree dual edge set cross a cut of dual vertices an even number of times?
- What goes wrong with the face-coloring requirement if a primal edge is a bridge?
- For the cube example, verify that \(S_2\) and \(S_3\) differ by the label on their shared spoke.