Dual Graphs and Face Coloring

The dual graph construction transforms faces into vertices and edges into edges, providing a powerful duality between vertex and face properties in planar graphs.

DefinitionPlanar Dual

For a connected plane graph $G$ , the planar dual $G^*$ is constructed by:

Place a vertex in each face of $G$
For each edge $e$ in $G$ , add an edge in $G^*$ connecting the two faces adjacent to $e$

The dual $G^*$ is also a planar graph. Moreover, $(G^*)^* = G$ (taking the dual twice returns to the original graph).

ExampleDual of $K_4$

$K_4$ drawn as a tetrahedron has 4 triangular faces. Its dual $G^*$ is also $K_4$ : place vertices at face centers, connect through shared edges. Thus $K_4$ is self-dual.

The cycle $C_n$ has dual $K_{1,n-1}$ (star graph): the cycle has 2 faces (inside and outside), connected by $n$ edges.

TheoremDual Graph Properties

For dual graphs $G$ and $G^*$ :

Vertices in $G^*$ correspond to faces in $G$ : $n(G^*) = f(G)$
Edges are same: $m(G^*) = m(G)$
Faces in $G^*$ correspond to vertices in $G$ : $f(G^*) = n(G)$
Cycles in $G$ correspond to minimal cuts in $G^*$

These properties establish deep structural connections.

Remark

Face coloring in $G$ is equivalent to vertex coloring in $G^*$ . The Four Color Theorem states every planar graph is 4-face-colorable, equivalently, $\chi(G^*) \leq 4$ for any planar graph $G^*$ . This famous result, proved in 1976 using computer-assisted methods, shows planar graphs have chromatic number at most 4.