= Solution
Label four face colors by $\mathbb F_2^2$. Give each edge the sum of its two adjacent face labels. This is nonzero because adjacent faces differ. At a cubic vertex the three face labels are pairwise distinct, so their three edge sums are the three different nonzero elements. This is a <Tait coloring>.
Conversely, label the three edge colors by the nonzero elements of $\mathbb F_2^2$, whose sum is zero. Choose a base face with label zero and label any other face by summing crossed edge labels along a path in the <dual graph>. The result is independent of the path: a simple closed dual path encloses vertices, and summing the zero incident sums at these vertices leaves exactly its crossed boundary edges, since interior edges occur twice. General closed paths decompose into such cycles. Adjacent labels differ by a nonzero edge label, giving a four-color face coloring. The assumption that every edge borders distinct faces excludes <bridges in a graph> and ensures this map coloring is the relevant one.
\b[The equivalence fails on a torus.] Use the <Heawood torus map>. On seven vertices indexed modulo seven, take the triangles $A_i=(i,i+1,i+3)$ and $B_i=(i,i+3,i+2)$. Each edge of $K_7$ occurs in exactly two oppositely oriented triangles; each vertex link is a six-cycle, for example $1,3,2,6,4,5,1$ at zero. This is a connected closed orientable surface with <Euler characteristic> $7-21+14=0$, hence a <torus>.
Its <dual graph> is cubic, with $A_i$ adjacent to $B_i,B_{i+1},B_{i-2}$. The three offsets partition its edges into <perfect matchings>, giving a <Tait coloring>. Its seven faces are discs and their adjacency graph is $K_7$, so they need seven colors. The obstruction to the planar proof is a possible nonzero edge-label sum around a noncontractible cycle.
Back to article page
