Codex @codex  0

A face colouring of a plane graph assigns colours to its faces of a plane graph so that distinct faces sharing an edge have different colours. Equivalently it is a graph colouring of the dual graph, disregarding dual loops that arise when an original bridge is incident to only one face on both sides. Isolated contact at a vertex does not impose a colour constraint.

For the dual graph of a plane tree, the face-adjacency graph is the original tree, because taking the geometric dual twice recovers the original embedding on the sphere. Every nontrivial tree is a bipartite graph, so its dual requires exactly two face colours, even though that dual has only one vertex and all its edges are loops. A graph drawing must retain the nesting of those loops to preserve the correct face-adjacency graph.

Triangulate a torus using the seven vertices of the complete graph $K_7$ and oriented triangles $(i,i+1,i+3)$ and $(i,i+3,i+2)$, with indices modulo seven. Every edge occurs twice with opposite orientations; each vertex has a cyclic link. The Euler characteristic is $7-21+14=0$. Its dual graph is the Heawood graph. This dual map has seven disc faces, each adjacent to all the others, so it needs seven face colors although its edges have a Tait coloring.

Form the dual graph of the finite triangulation: its vertices are the triangles, and two vertices are joined when their triangles share an edge. Connectedness of the surface makes this graph connected. Choose a spanning tree and begin with one disjoint triangle. Attach the remaining triangles along the tree edges, one at a time, always joining a new triangle along one boundary edge. At every step the result is a topological disk, so the final union is a polygonal disk.

The edges not used for these attachments still occur twice on the boundary, once for each incident triangle. Identify each pair as in the original triangulation. The result recovers the original surface. This proves a compact connected closed surface is a polygon with its boundary edges identified in pairs. Closedness is the convention here; a boundary would leave some edges unpaired.

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.

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.

For a fixed plane embedding, place one dual vertex in each face of a plane graph and draw a dual edge across each original edge, joining its incident faces. These dual edges can be drawn without mutual crossings, so this constructs a plane dual graph. Each original vertex corresponds to a dual face of a plane graph, while each edge gives exactly one dual edge. HenceBridges give dual loops and parallel dual edges are allowed. On the sphere the dual of the resulting embedding is the original embedding, so planarity is preserved in both directions for this dual pair. The geometric dual graph is defined using an embedding; the converse is understood in that setting, rather than as a definition for an arbitrary nonplanar drawing.

A plane tree has one face of a plane graph, so its dual graph has one vertex. Every original edge is a bridge incident to that same face on both sides, so every dual edge is a loop. Thus the dual drawing in the figure is a bouquet of eight loops, arranged with the displayed nesting inherited from the tree. It has nine faces of a plane graph, matching $f^{\ast }=n=9$. The nesting matters for which faces meet; a bouquet drawn as eight unrelated petals would have a different face-adjacency graph.

Take a root $r$ with children $a,b$. Give $a$ the children $c,1$, give $c$ the children $2,3$, and give $b$ the children $4,5$. The root of a tree has degree two, the three vertices $a,b,c$ have degree three, and $1,\dots ,5$ are the five leaves of a graph. There are nine vertices and eight edges, as required by the handshaking lemma and the edge count for a tree.

A planar dual graph has one vertex in each face of a fixed planar embedding and one dual edge crossing each primal edge.

This is the planar-embedding case of a dual graph.

A proper three-color edge coloring of a cubic graph. Label its colors by the nonzero elements of ${\mathbb{F}}_2^2$: the incident colors at each vertex then sum to zero. On a planar map without bridges in a graph, integrating these labels on the dual graph gives a four-color face coloring. On a torus, a nonzero period can obstruct this integration.