Triangulations and Cubic Duals

Triangulating a Plane Graph

A plane graph carries both a graph structure and a particular embedding: its edges are drawn without crossings, and the regions of the complement are its faces. For the Four Color Theorem, a useful simplification is to add edges until every face is triangular. The resulting graph has more constraints than the original, so a coloring of the larger graph automatically gives a coloring of the original. Its dual also has a special form: every vertex has degree three.

All primal graphs in this tutorial are finite and simple. A plane graph is a graph together with a fixed crossing-free embedding in the plane; equivalently, we may regard the plane as a sphere with one point removed. A face is a connected region of the complement of the embedded graph. Face boundaries are counted by their edge incidences, so an edge appearing twice in a boundary walk would be counted twice.

In a plane triangulation, each edge has a face on each side, and the two incident faces are distinct. Its dual may have parallel edges: for example, the two faces of an embedded triangle share all three primal edges. Thus, when discussing the dual’s degree, edges are counted with multiplicity. A graph is cubic if every vertex has degree three.

A standard elementary augmentation fact will be useful: every simple plane graph with at least three vertices is a subgraph of a plane triangulation on the same vertex set. One way to see the idea is to choose an edge-maximal simple plane supergraph on that vertex set. A missing edge that can be drawn in a face would contradict maximality; the standard maximal-planar argument shows that a maximal simple plane graph has triangular faces. In applying the fact, the embedding matters: the added edges must be drawable in faces without crossings. The four-coloring implication below needs only that such an augmentation has been made, not a particular construction of it.

Why the Dual Is Cubic

Proof. Let \(T\) be a plane triangulation and let \(T^*\) be its plane dual. A vertex \(f^*\) of \(T^*\) corresponds to a face \(f\) of \(T\). The boundary of \(f\) is a triangle, so it has exactly three edge incidences. Each of those three primal edges contributes one dual edge incident with \(f^*\). Therefore \(\deg_{T^*}(f^*)=3\). This applies to every face \(f\), hence every vertex of \(T^*\) has degree three. If two faces share more than one edge, the corresponding dual edges are parallel and are counted separately, as required by the degree calculation. \(\square\)

This result is local: it follows directly from the three sides of each face. The global counts provide a useful independent check. For a plane triangulation with \(n\ge3\) vertices, let \(m\) be its number of edges and \(f\) its number of faces. Euler’s formula on the sphere gives \(n-m+f=2\). Counting face-edge incidences gives \(3f=2m\), since every face has three sides and every edge is incident with two faces. Solving yields \(m=3n-6\) and \(f=2n-4\). Thus the dual has \(2n-4\) vertices and \(3n-6\) edges; its total degree is \(2(3n-6)=3(2n-4)\), consistent with degree three at every vertex.

Why Adding Edges Preserves the Four-Coloring Implication

A proper vertex coloring assigns colors to vertices so that the endpoints of every edge have different colors. If \(G\) is a subgraph of \(H\), then every proper coloring of \(H\) restricts to a proper coloring of \(G\): each edge of \(G\) is also an edge of \(H\), so its endpoints already have different colors in \(H\). In particular, this holds when \(H\) is formed by adding edges to a plane graph \(G\).

Proof. Suppose \(T\) has a proper coloring with at most four colors. Restrict this assignment to \(V(G)\). For each edge \(uv\in E(G)\), we also have \(uv\in E(T)\), so the colors of \(u\) and \(v\) differ. The restricted assignment is therefore a proper coloring of \(G\) using at most four colors. Now let \(G\) be any simple planar graph with at least three vertices, choose a plane embedding, and augment it to a plane triangulation \(T\) as above. If every such \(T\) is four-colorable, the restriction gives a four-coloring of \(G\). Graphs with fewer than three vertices are four-colorable directly: with zero vertices there is nothing to color, and with one or two vertices at most two colors are needed. \(\square\)

The implication is one-way for a particular graph and its augmentation. Adding an edge imposes an extra constraint, so a coloring of the smaller graph need not extend to the larger one. The reduction works in the useful direction: proving the four-color statement for all triangulations suffices to prove it for all planar graphs.

Triangulations in Tait’s Setting

Tait’s reformulation of the Four Color Theorem uses proper edge colorings of cubic plane graphs. A proper edge coloring assigns colors to edges so that any two edges sharing a vertex receive different colors. In a cubic graph, exactly three edges meet at each vertex, so a proper coloring with three edge colors uses all three colors once at every vertex.

The dual of a plane triangulation is precisely cubic, by the theorem proved above. Thus triangulated primal graphs place the dual in Tait’s natural setting. Under plane duality, primal faces become dual vertices, and primal edges become dual edges. The standard dual formulation of Tait’s result says that four-colorability of a plane triangulation corresponds to a proper three-edge-coloring of its cubic dual; the Four Color Theorem can equivalently be expressed as the assertion that every bridgeless cubic planar graph is three-edge-colorable. The full translation between face colors and edge colors is developed separately; here the key structural point is that triangular faces produce degree-three dual vertices.

For triangulations, the dual is also bridgeless. One standard plane-duality fact is that a dual edge is a bridge exactly when its corresponding primal edge is a loop. A triangulation is simple and therefore has no loops, so its dual has no bridges. This explains why the duals arising here belong to the bridgeless cubic class in Tait’s formulation. The degree-three conclusion itself does not require this additional fact; it follows just by counting the three edge incidences around each triangular face.

Common Pitfalls

Confusing degree with the number of distinct neighbors. The dual of an embedded triangle has two vertices joined by three parallel edges. Each vertex has degree three, even though it has only one distinct neighbor. The theorem counts incident edges with multiplicity.

Assuming a coloring of the original graph extends after adding edges. Added edges can join vertices that previously shared a color. What is guaranteed is restriction: a coloring of the augmented triangulation remains proper after the added edges are discarded.

Using triangular bounded faces but ignoring the outer face. A plane triangulation requires every face, including the unbounded face in the plane drawing, to be a triangle. Equivalently, on the sphere every face is triangular. A graph with triangular interior regions but a nontriangular outer boundary is not yet a plane triangulation.