From Faces to Dual Vertices
Coloring a map means assigning colors to its regions so that the required neighboring regions differ in color. A plane dual turns those regions into vertices and records edge-by-edge which regions meet. This makes face-coloring a vertex-coloring problem, but there is an important detail: an edge may have the same face on both sides. Its dual is then a loop, and a loop cannot have different-colored endpoints. Whether that loop obstructs coloring depends on the precise convention used for map coloring.
All graphs below are finite. A plane graph is a graph drawn in the plane with edges meeting only at common endpoints. Its faces are the connected regions of the complement of the drawing, including the unbounded region. An edge has two sides in the embedding; the faces incident with those sides may be distinct or may be the same face. We use the standard plane dual: it has one vertex for each face, and each primal edge gives a dual edge joining the vertices for its two incident faces. If those faces are the same, the dual edge is a loop. Different primal edges can give parallel dual edges.
This strict convention counts the two sides of every edge, even when they belong to one face. In the common region-coloring convention, only distinct regions are required to have different colors; a region is not considered adjacent to itself. Under that convention a bridge’s dual loop imposes no constraint and is ignored. We will state both interpretations where relevant, so the correspondence is exact rather than dependent on an unstated convention.
The Exact Correspondence
Proof. Write \(F(G)\) for the set of faces of \(G\). By definition, the vertices of \(G^*\) are exactly the elements of \(F(G)\). Given a strict face-coloring \(c:F(G)\to C\), assign to each dual vertex \(v_F\) the color \(c(F)\). For any primal edge \(e\), let \(F_1,F_2\) be the faces on its two sides. The dual edge corresponding to \(e\) joins \(v_{F_1}\) to \(v_{F_2}\). Since \(c\) is strict, \(c(F_1)\ne c(F_2)\), so the dual edge has differently colored endpoints. This holds for every dual edge, making the assignment a proper coloring of \(G^*\).
Conversely, given a proper coloring of \(G^*\), color each face \(F\) of \(G\) with the color of \(v_F\). For every primal edge \(e\), its dual edge joins the vertices corresponding to the two incident faces. Properness of the dual coloring therefore says those two faces have different colors. The resulting face-coloring is strict. These two constructions reverse each other because each face corresponds to exactly one dual vertex and the color is transferred unchanged. If an edge has the same face \(F\) on both sides, its dual edge is a loop at \(v_F\); properness would require the color of \(v_F\) to differ from itself, which no color can satisfy. Thus both coloring sets are empty in that case. \(\square\)
The theorem concerns color assignments from the same palette, not just the existence of some coloring. It also explains why parallel dual edges cause no extra difficulty: each one records a constraint, but repeated constraints between the same two vertices say the same thing.
Proof. When \(G^*\) has no loops, the theorem gives a correspondence for each palette of \(k\) colors. Thus a strict face-coloring using at most \(k\) colors exists exactly when a proper vertex-coloring of \(G^*\) using at most \(k\) colors exists. The least such \(k\) is therefore \(\chi(G^*)\), by the definition of chromatic number. If the dual has a loop, the theorem shows that no strict face-coloring exists. \(\square\)
Worked Examples
Worked Example: A Triangle and Its Two Faces
Draw the triangle \(G\) with \(V(G)=\{1,2,3\}\) and \(E(G)=\{12,23,31\}\) in the usual plane embedding. It has an interior face \(F_{\mathrm{in}}\) and an exterior face \(F_{\mathrm{out}}\). Each of the three edges has these two faces on its sides, so the dual has vertices \(F_{\mathrm{in}},F_{\mathrm{out}}\) and three parallel edges between them.
With palette \(C=\{\text{red},\text{blue},\text{green}\}\), choose a color for \(F_{\mathrm{in}}\): there are \(3\) choices. The exterior face must have a different color, leaving \(2\) choices. Thus there are \(3\cdot2=6\) strict face-colorings. The dual gives the same count: its two vertices must differ in color, so there are also \(3\cdot2=6\) proper vertex-colorings. The three parallel edges impose the same inequality three times, not three different inequalities.
Check: Directly on the map, every edge separates the interior from the exterior, so the only restriction is that these two faces differ. The count \(3\cdot2=6\) agrees with the dual count.
Worked Example: A Bridge Produces a Dual Loop
Let \(G\) have \(V(G)=\{a,b\}\), \(E(G)=\{ab\}\), and draw its single edge as a line segment in the plane. The complement has one face \(F\), incident with both sides of \(ab\). Hence \(G^*\) has one vertex \(F\) and one loop at that vertex.
For strict face-coloring, the edge requires the face on one side to differ from the face on the other side. Both sides are \(F\), so the requirement is \(c(F)\ne c(F)\), which is impossible for every palette. On the dual side, the loop likewise requires its vertex’s color to differ from itself. The two impossibility statements match exactly.
Under the usual region-coloring convention, there are no two distinct regions sharing this edge: there is only one region. That convention permits the one face to receive any chosen color, so for a palette of \(q\) colors there are \(q\) assignments. This does not contradict the theorem; it is a different coloring rule. The ordinary region-coloring version corresponds to coloring the dual after ignoring loops.
Check: The primal edge has the same face on both sides, so its dual edge has identical endpoints. This verifies directly that the dual edge is a loop and explains why the strict, but not the ordinary region, convention forbids a coloring.
Worked Example: A Square with a Diagonal
Draw \(G\) as a square with vertices \(1,2,3,4\) in cyclic order and a diagonal \(13\). Thus \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,41,13\}\). There are three faces: the two triangular interior faces \(F_1,F_2\), separated by \(13\), and the exterior face \(F_0\). The diagonal gives a dual edge \(F_1F_2\). Each triangular face also meets the exterior along two square edges, giving two parallel dual edges from \(F_1\) to \(F_0\), and two from \(F_2\) to \(F_0\).
Use a palette with \(3\) colors. First color \(F_0\), with \(3\) choices. The face \(F_1\) must differ from \(F_0\), giving \(2\) choices. The face \(F_2\) must differ from \(F_0\) and from \(F_1\), giving \(1\) choice. There are therefore \(3\cdot2\cdot1=6\) strict face-colorings.
Independently count proper colorings of the dual. Its constraints are \(F_1\ne F_0\), \(F_2\ne F_0\), and \(F_1\ne F_2\); repeated parallel edges do not change these conditions. Choose \(F_0\) in \(3\) ways, \(F_1\) in \(2\) ways after that, and \(F_2\) in \(1\) way. The dual count is again \(6\).
Check: The five primal edges account for the five dual edges: one from the diagonal and four from the square boundary. The two parallel edges at each face-to-exterior pair repeat an existing color constraint, so the three distinct pairwise inequalities yield the independently verified count \(3\cdot2\cdot1=6\).
Using the Correspondence Correctly
For a loopless dual, the translation is direct: a face-coloring problem becomes an ordinary vertex-coloring problem on the dual. The geometry is useful for constructing that dual, but once the dual is known, the coloring conditions are purely graph-theoretic. Parallel edges can be retained in the dual definition, yet they do not alter which vertex-colorings are proper.
Loops require an explicit choice of convention. In strict edge-side coloring, every edge demands different colors on its two sides. A bridge has the same face on both sides, so it makes strict coloring impossible. In ordinary map coloring, adjacency is usually between distinct regions; then that bridge does not create a self-adjacency constraint. The corresponding dual statement is to delete or ignore loops before coloring. In either convention, edges between distinct faces still impose exactly the dual’s endpoint inequality.
Common mistake: A tempting but incorrect claim is, “Every plane map with a bridge is uncolorable because its dual has a loop.” That conclusion is correct only for strict edge-side coloring. For example, the one-edge graph in the previous example has one region, which can be assigned red under ordinary region-coloring; there are no two distinct regions whose colors must differ. The correction is to state the coloring convention first: a loop blocks proper vertex-coloring, while ordinary region-coloring ignores a loop because it does not join two distinct faces.
Another error is to count parallel dual edges as separate coloring choices or as additional colors. They are constraints, not choices: if two dual vertices are joined by one or several edges, proper coloring requires the same single condition that their colors differ. What matters for the face-coloring translation is which pairs of distinct faces share an edge, together with whether an edge has the same face on both sides under the strict convention.
Check Your Understanding
For each question, specify whether you are using strict edge-side coloring or ordinary region-coloring when a face may occur on both sides of an edge.
- A plane graph has an edge whose two sides belong to the same face. What does the corresponding dual edge look like, and what does it imply under strict face-coloring?
- Why do two parallel edges between the same dual vertices impose only one distinct-color condition?
- A plane map has three faces, and its dual has one edge between each pair of distinct vertices. How many colors are required for strict face-coloring?
- Explain how a proper coloring of the dual gives a face-coloring, and identify the step that uses the definition of the dual.
- Under ordinary region-coloring, what adjustment to the dual handles bridges, and why?