A Plane Graph to Work With
A proper three-edge-coloring of a cubic plane graph is called a Tait coloring. It can be translated into a coloring of the graph’s faces: faces that share an edge must receive different colors. This tutorial carries out both steps on one graph, checking the edge colors at every vertex and the face colors across every edge. The example also shows why a four-color palette does not mean that four colors must appear.
All graphs below are finite and simple. A plane graph is a graph drawn in the plane without edge crossings, together with the faces determined by that drawing. A graph is cubic if every vertex has degree three. An edge is a bridge if deleting it increases the number of connected components; a graph is bridgeless if it has no bridges. The dual graph has one vertex for each face of the plane graph, with dual vertices adjacent when their faces share an edge.
We use the cube graph with top vertices \(a,b,c,d\), bottom vertices \(A,B,C,D\), and corresponding vertical edges. Its vertex and edge sets are
Take its plane embedding to have faces \(T=abcd\), \(B=ABCD\), \(F_{ab}=abBA\), \(F_{bc}=bcCB\), \(F_{cd}=cdDC\), and \(F_{da}=daAD\), where each listed boundary is a cycle. These six boundaries and the twelve edges specify the embedding for our purposes. Every vertex has degree three. The graph is connected, and every listed edge lies on at least one of these cycles. An edge on a cycle is not a bridge: the rest of the cycle still connects its endpoints after that edge is deleted. Thus this plane graph is bridgeless.
Worked Tait Coloring
Worked Example: Color Every Edge of the Cube
Use the explicitly defined cube graph \(G=(V,E)\) above. Give the top and bottom cycle edges the same alternating pattern, and color every vertical edge with color \(3\):
Here an equation such as \(ab=1\) means that edge \(ab\) receives color \(1\). To check properness, list the three incident edges and their colors at every vertex:
| Vertex | Incident edge colors | Distinct? |
|---|---|---|
| \(a\) | \(ab:1,\ ad:2,\ aA:3\) | Yes |
| \(b\) | \(ab:1,\ bc:2,\ bB:3\) | Yes |
| \(c\) | \(bc:2,\ cd:1,\ cC:3\) | Yes |
| \(d\) | \(cd:1,\ da:2,\ dD:3\) | Yes |
| \(A\) | \(aA:3,\ AB:1,\ DA:2\) | Yes |
| \(B\) | \(bB:3,\ AB:1,\ BC:2\) | Yes |
| \(C\) | \(cC:3,\ BC:2,\ CD:1\) | Yes |
| \(D\) | \(dD:3,\ CD:1,\ DA:2\) | Yes |
Each vertex has one incident edge of each color, so the coloring is proper. The check covers all eight vertices and therefore all pairs of incident edges. As a separate count, the edge list contains \(4+4+4=12\) edges, and the assignments above color \(4+4+4=12\) edges, with none omitted.
From Edge Colors to Face Colors
For this construction, encode each edge color by a nonzero binary pair: \(1\mapsto(1,0)\), \(2\mapsto(0,1)\), and \(3\mapsto(1,1)\). Add pairs coordinatewise modulo \(2\), denoting this operation by \(\oplus\). For example, \((1,0)\oplus(0,1)=(1,1)\), while \((1,0)\oplus(1,0)=(0,0)\).
Assign a pair to a face so that the pairs on the two sides of each edge differ by the pair for that edge’s color. For the coloring above, set the pair of \(T\) to \((0,0)\). Across edges \(ab\) and \(da\), the adjacent side faces receive the pairs for colors \(1\) and \(2\), respectively. Continuing around the cube gives the following assignments. The table also checks all twelve edges; the pair difference is the first face pair \(\oplus\) the second face pair.
| Edge | Faces on its sides | Edge color | Pair difference |
|---|---|---|---|
| \(ab\) | \(T,F_{ab}\) | 1 | \((1,0)\) |
| \(bc\) | \(T,F_{bc}\) | 2 | \((0,1)\) |
| \(cd\) | \(T,F_{cd}\) | 1 | \((1,0)\) |
| \(da\) | \(T,F_{da}\) | 2 | \((0,1)\) |
| \(AB\) | \(B,F_{ab}\) | 1 | \((1,0)\) |
| \(BC\) | \(B,F_{bc}\) | 2 | \((0,1)\) |
| \(CD\) | \(B,F_{cd}\) | 1 | \((1,0)\) |
| \(DA\) | \(B,F_{da}\) | 2 | \((0,1)\) |
| \(aA\) | \(F_{da},F_{ab}\) | 3 | \((1,1)\) |
| \(bB\) | \(F_{ab},F_{bc}\) | 3 | \((1,1)\) |
| \(cC\) | \(F_{bc},F_{cd}\) | 3 | \((1,1)\) |
| \(dD\) | \(F_{cd},F_{da}\) | 3 | \((1,1)\) |
For example, across \(aA\), the two face pairs are \((0,1)\) and \((1,0)\); their difference is \((0,1)\oplus(1,0)=(1,1)\), which is the pair for color \(3\). The table makes the same comparison for every edge.
Proof. Let two faces share an edge, and suppose the edge color is represented by a nonzero pair \(q\). By the assignment condition, if one face has pair \(p\), the other has pair \(p\oplus q\). If the pairs were equal, then \(p=p\oplus q\). Adding \(p\) to both sides modulo \(2\) would give \((0,0)=q\), contradicting that \(q\) is nonzero. Thus the two faces have different pairs. This applies to every edge, so the face coloring is proper. \(\square\)
In the table, the face assignments are \(T=B=(0,0)\), \(F_{ab}=F_{cd}=(1,0)\), and \(F_{bc}=F_{da}=(0,1)\). They use three distinct pairs, not four. Each pair is a valid choice from the palette of four binary pairs, but the fourth pair \((1,1)\) is unused in this assignment. A proper coloring from a palette of four colors is still a proper four-coloring when it happens to use only three.
Worked Example: Check the Dual Coloring by Faces
Use the same explicitly defined graph \(G=(V,E)\) and the first edge coloring. Check face by face that no two faces sharing an edge have the same pair.
The face pairs are \(T=(0,0)\), \(B=(0,0)\), \(F_{ab}=(1,0)\), \(F_{bc}=(0,1)\), \(F_{cd}=(1,0)\), and \(F_{da}=(0,1)\). Across the four top edges, \(T\) is adjacent in turn to \(F_{ab},F_{bc},F_{cd},F_{da}\), whose pairs differ from \((0,0)\). Across the four bottom edges, \(B\) is adjacent to the same four side faces, again with different pairs.
The vertical edges join consecutive side faces: \(aA\) joins \(F_{da}\) to \(F_{ab}\), \(bB\) joins \(F_{ab}\) to \(F_{bc}\), \(cC\) joins \(F_{bc}\) to \(F_{cd}\), and \(dD\) joins \(F_{cd}\) to \(F_{da}\). In each case the pairs are \((0,1)\) and \((1,0)\), which are different. These checks cover all \(4+4+4=12\) edges, so every adjacent face pair is properly colored.
Check: the boundary list has two faces of length \(4\) and four side faces of length \(4\), giving \(6\cdot4=24\) face-edge incidences. Each of the \(12\) edges is incident with two faces, also giving \(12\cdot2=24\). The two counts agree.
A Coloring That Uses All Four Face Colors
Worked Example: Reverse the Bottom-Cycle Colors
Again use the explicitly defined cube graph \(G=(V,E)\). Keep the top-cycle and vertical-edge colors from the first example, but assign the bottom edges \(AB=2\), \(BC=1\), \(CD=2\), and \(DA=1\). This remains a proper Tait coloring: at \(A,B,C,D\), respectively, the incident color lists are \((3,2,1)\), \((3,2,1)\), \((3,1,2)\), and \((3,2,1)\), each containing all three colors.
Keep \(T=(0,0)\) and the four side-face pairs \(F_{ab}=(1,0)\), \(F_{bc}=(0,1)\), \(F_{cd}=(1,0)\), \(F_{da}=(0,1)\). Across bottom edge \(AB\), color \(2\) has pair \((0,1)\), so the bottom face must have pair \(F_{ab}\oplus(0,1)=(1,0)\oplus(0,1)=(1,1)\). The other three bottom edges give the same result: \(F_{bc}\oplus(1,0)=(0,1)\oplus(1,0)=(1,1)\); \(F_{cd}\oplus(0,1)=(1,0)\oplus(0,1)=(1,1)\); and \(F_{da}\oplus(1,0)=(0,1)\oplus(1,0)=(1,1)\). Thus \(B=(1,1)\).
Now \(T,B,F_{ab},F_{bc},F_{cd},F_{da}\) have pairs \((0,0),(1,1),(1,0),(0,1),(1,0),(0,1)\), respectively. The four distinct pairs \((0,0),(1,1),(1,0),(0,1)\) all occur. At the top edges, the differences from \(T\) are \((1,0)\) on \(ab,cd\) and \((0,1)\) on \(bc,da\), matching colors \(1,2,1,2\). At the bottom edges, the differences from \(B\) to \(F_{ab},F_{bc},F_{cd},F_{da}\) are \((0,1),(1,0),(0,1),(1,0)\), matching bottom colors \(2,1,2,1\). Across each vertical edge, the side-face difference is \((1,1)\), matching color \(3\). Thus all twelve edge checks pass, and all four face colors are used.
Check: each top and bottom face pair differs from each of its four neighboring side-face pairs, and each vertical edge joins side faces with pairs \((1,0)\) and \((0,1)\). These are the complete set of adjacencies, so the four-pair face assignment is proper.
Why the Checks Matter
The two edge colorings differ only in the pattern on the bottom cycle, yet their induced face assignments differ: the first has three distinct face colors and the second has four. This illustrates the practical value of checking the face pairs against the edge colors rather than assuming that every Tait coloring uses every face color. The target is a proper coloring from a palette of at most four colors; using fewer is allowed.
Common pitfall: counting the palette instead of the colors used. In the first assignment, \(T\) and \(B\) both receive \((0,0)\); \(F_{ab}\) and \(F_{cd}\) both receive \((1,0)\); and \(F_{bc}\) and \(F_{da}\) both receive \((0,1)\). A mistaken count might say “four distinct pairs” because four is the palette size. The correction is to list the distinct values: \(\{(0,0),(1,0),(0,1)\}\), which has size \(3\). The remaining palette pair is \((1,1)\).
A second useful check is to verify local edge properness before attempting the dual coloring. A single vertex with two incident edges of the same color invalidates the Tait coloring, even if the face-pair list looks plausible. Conversely, once a proper edge coloring and face assignments are supplied, checking every edge in the plane graph verifies the dual face coloring directly.
Check Your Understanding
Use the cube graph and face boundaries specified in this tutorial when a question refers to the cube.
- For the first Tait coloring, list the colors incident with \(C\) and \(D\), and verify they are distinct at each vertex.
- For the first face assignment, what pair difference occurs across edge \(cC\), and which edge color does it represent?
- How many distinct face pairs occur in the first assignment? Name them and identify the unused pair from the four-pair palette.
- For the second Tait coloring, calculate the pair of \(B\) independently from edge \(BC\), using the pair of \(F_{bc}\).
- Explain why checking that every face pair differs across each of the twelve edges proves properness of the dual face coloring.