The Face-Pair Rule
A face coloring records which regions of a plane graph meet across each edge. In a cubic plane graph, the three edges at a vertex lie between three consecutive face sectors. A proper four-coloring of the faces makes those three sector colors distinct. That local fact is what allows the face colors to determine a proper edge coloring.
Throughout, a plane graph is a graph drawn in the plane with edges meeting only at common endpoints. We consider finite, loopless plane graphs in which every vertex has degree three; parallel edges are allowed. A face is a region of the drawing. Two faces are incident with an edge when they lie on its two sides. A proper face coloring assigns colors to faces so that the two faces incident with every edge have different colors. A proper edge coloring assigns colors to edges so that any two edges sharing a vertex have different colors. In a cubic graph, this means the three edges at each vertex must receive three distinct colors.
Equivalently, the unordered face-color pairs are grouped as follows. The order of the two incident faces does not matter.
| Edge color | Incident face-color pairs |
|---|---|
| \(\mathsf{R}\) | \(12,\ 34\) |
| \(\mathsf{B}\) | \(13,\ 24\) |
| \(\mathsf{G}\) | \(14,\ 23\) |
For example, the pair \(24\) receives \(\mathsf{B}\), because the codes \(01\) and \(11\) differ by \(10\). The rule groups the six possible pairs of distinct face colors into three classes. It does not mean that an edge is colored by either one of its incident face colors; it is the pair that determines its edge color.
Why the Rule Works at a Vertex
Proof. Let the three sector colors be \(a,b,c\), with \(a,b,c\) distinct. The three incident edges separate the sector pairs \(ab\), \(bc\), and \(ca\). Represent each color by its two-bit code. The edge-color code for a pair \(x,y\) is the bitwise difference of their codes, which in two-bit arithmetic is their exclusive-or. Suppose two of the three resulting codes were equal, for example \(a\mathbin{\mathrm{xor}}b=a\mathbin{\mathrm{xor}}c\). Applying exclusive-or with \(a\) to both sides gives \(b=c\), contradicting that the sector colors are distinct. The same argument applies to any two of the three pairs. Thus all three edge colors are distinct. \(\square\)
Proof. Fix a vertex \(v\). Because \(G\) is loopless and has degree three, a small disk around \(v\) meets the drawing in three edge segments. These segments divide the disk into three sectors, each belonging to a face. Each incident edge separates two consecutive sectors. Properness of the face coloring says that the colors in those two sectors are different across each of the three edges. Consequently, the three sector colors are pairwise distinct: each pair of sectors is separated by one of the three incident edges. The Lemma now applies to these three colors and their three incident edges, so those edges receive distinct colors. Since \(v\) was arbitrary, this holds at every vertex. \(\square\)
The proof uses only a local condition: the three sectors around each vertex must have distinct colors. The global requirement that the coloring be proper guarantees that condition at every vertex simultaneously. A proper face coloring with only three of the four available colors still works; the argument does not require all four colors to appear.
Worked Examples
Worked Example: The Tetrahedron Drawing
Let \(G\) have vertex set \(\{a,b,c,d\}\) and edge set \(\{ab,ac,ad,bc,bd,cd\}\), drawn as a triangle \(abc\) with \(d\) inside and joined to all three boundary vertices. Its faces are \(F_0=abc\), \(F_1=abd\), \(F_2=bcd\), and \(F_3=cad\). Give these faces colors \(1,2,3,4\), respectively.
Check properness across each edge: \(ab\) separates \(F_0,F_1\), with colors \(1,2\); \(bc\) separates \(F_0,F_2\), with colors \(1,3\); \(ca\) separates \(F_0,F_3\), with colors \(1,4\); \(ad\) separates \(F_1,F_3\), with colors \(2,4\); \(bd\) separates \(F_1,F_2\), with colors \(2,3\); and \(cd\) separates \(F_2,F_3\), with colors \(3,4\). Every pair consists of different colors.
Apply the table edge by edge: \(ab\) has pair \(12\), so it receives \(\mathsf{R}\); \(bc\) has \(13\), so it receives \(\mathsf{B}\); \(ca\) has \(14\), so it receives \(\mathsf{G}\); \(ad\) has \(24\), so it receives \(\mathsf{B}\); \(bd\) has \(23\), so it receives \(\mathsf{G}\); and \(cd\) has \(34\), so it receives \(\mathsf{R}\).
Check the edges at each vertex: at \(a\), \(ab,ac,ad\) have colors \(\mathsf{R},\mathsf{G},\mathsf{B}\); at \(b\), \(ab,bc,bd\) have \(\mathsf{R},\mathsf{B},\mathsf{G}\); at \(c\), \(ca,bc,cd\) have \(\mathsf{G},\mathsf{B},\mathsf{R}\); and at \(d\), \(ad,bd,cd\) have \(\mathsf{B},\mathsf{G},\mathsf{R}\). Each list contains all three edge colors, as the theorem predicts.
Worked Example: A Cube with Only Three Face Colors
Take the plane drawing of a square prism. Its vertices are \(\{a,b,c,d,A,B,C,D\}\), and its edges are \(\{ab,bc,cd,da,AB,BC,CD,DA,aA,bB,cC,dD\}\). The faces are the top \(abcd\), the bottom \(ABCD\), and the four side faces \(abBA,bcCB,cdDC,daAD\). Give the top face color \(1\), the bottom face color \(2\), the side faces \(abBA,cdDC\) color \(3\), and \(bcCB,daAD\) color \(4\).
The top face meets only side faces of colors \(3\) and \(4\), both different from \(1\); the bottom face meets only side faces of colors \(3\) and \(4\), both different from \(2\). Across the four vertical edges \(aA,bB,cC,dD\), consecutive side faces have colors \(4,3\); \(3,4\); \(4,3\); and \(3,4\), respectively. Thus every edge separates differently colored faces.
The top edges \(ab,bc,cd,da\) have face pairs \(13,14,13,14\), so their edge colors are \(\mathsf{B},\mathsf{G},\mathsf{B},\mathsf{G}\). The bottom edges \(AB,BC,CD,DA\) have pairs \(23,24,23,24\), so their colors are \(\mathsf{G},\mathsf{B},\mathsf{G},\mathsf{B}\). Each vertical edge has pair \(34\), so \(aA,bB,cC,dD\) all receive \(\mathsf{R}\).
For a vertex check, at \(a\) the edges \(ab,da,aA\) have colors \(\mathsf{B},\mathsf{G},\mathsf{R}\); at \(b\), \(ab,bc,bB\) have \(\mathsf{B},\mathsf{G},\mathsf{R}\); at \(c\), \(bc,cd,cC\) have \(\mathsf{G},\mathsf{B},\mathsf{R}\); and at \(d\), \(cd,da,dD\) have \(\mathsf{B},\mathsf{G},\mathsf{R}\). The same check on the bottom vertices gives one edge of each color at \(A,B,C,D\). The face coloring uses only three colors, but it still produces a proper edge coloring.
Worked Example: The Triangular Prism
Let \(G\) have vertices \(\{a,b,c,A,B,C\}\) and edges \(\{ab,bc,ca,AB,BC,CA,aA,bB,cC\}\), drawn as two triangular faces joined by three rectangular faces. Name the triangles \(T=abc\) and \(U=ABC\), and the rectangles \(R_{ab}=abBA\), \(R_{bc}=bcCB\), and \(R_{ca}=caAC\). Color the rectangles \(1,2,3\), respectively, and color both triangles \(4\).
The rectangles meet each other across the vertical edges: \(R_{ab}\) meets \(R_{bc}\) across \(bB\), \(R_{bc}\) meets \(R_{ca}\) across \(cC\), and \(R_{ca}\) meets \(R_{ab}\) across \(aA\). Their colors \(1,2,3\) are pairwise different. Each triangle meets all three rectangles, and color \(4\) differs from \(1,2,3\). Therefore this is a proper face coloring.
The top edges \(ab,bc,ca\) have pairs \(14,24,34\), and hence colors \(\mathsf{G},\mathsf{B},\mathsf{R}\). The bottom edges \(AB,BC,CA\) have the same respective pairs, so their colors are also \(\mathsf{G},\mathsf{B},\mathsf{R}\). The vertical edges \(aA,bB,cC\) have pairs \(13,12,23\), so their colors are \(\mathsf{B},\mathsf{R},\mathsf{G}\).
At \(a\), the incident edges \(ab,ca,aA\) have colors \(\mathsf{G},\mathsf{R},\mathsf{B}\); at \(b\), \(ab,bc,bB\) have \(\mathsf{G},\mathsf{B},\mathsf{R}\); and at \(c\), \(bc,ca,cC\) have \(\mathsf{B},\mathsf{R},\mathsf{G}\). At \(A\), the edges \(AB,CA,aA\) have \(\mathsf{G},\mathsf{R},\mathsf{B}\); at \(B\), \(AB,BC,bB\) have \(\mathsf{G},\mathsf{B},\mathsf{R}\); and at \(C\), \(BC,CA,cC\) have \(\mathsf{B},\mathsf{R},\mathsf{G}\). Each vertex passes the distinct-color check.
Why the Pairing Matters
The rule is a specific grouping of the six possible pairs, not an arbitrary assignment of pairs to three edge colors. At a vertex whose sectors have colors \(1,2,3\), the incident edge pairs are \(12,23,31\). The prescribed rule gives these the distinct colors \(\mathsf{R},\mathsf{G},\mathsf{B}\). If instead one incorrectly assigns both \(12\) and \(13\) to \(\mathsf{R}\), then at a vertex with sector colors \(1,2,3\), the two edges separating \(1\) from \(2\) and \(1\) from \(3\) would both receive \(\mathsf{R}\). The edge coloring would fail to be proper. The bit-pair encoding prevents this: distinct face colors give distinct pairwise differences among the three sector pairs.
This construction supplies one direction of the connection between face coloring and edge coloring: a proper four-coloring of faces gives a proper three-coloring of the edges of a cubic plane graph. Its value is that it converts a global coloring of regions into a local coloring constraint at each vertex. The proof needs no choice of a starting vertex or special orientation; the same pair rule applies to every edge.
Check Your Understanding
Use the pair table and the local argument to answer the following.
- What edge color does an edge receive if its incident face colors are \(2\) and \(3\)?
- Why must the three sector colors around a cubic vertex be pairwise distinct under a proper face coloring?
- In the cube example, why is it valid that the same face-color pair \(34\) occurs on four different edges?
- Show directly from the table that the pairs \(12,23,31\) receive three distinct edge colors.
- Which part of the proof would need revision if loops were allowed in the cubic plane graph?