What Does the Dual Remember?
A plane graph is a graph drawn on the sphere (equivalently, in the plane with one point added) so that edges meet only at their common endpoints. Its faces are the connected regions left after removing the drawing. The geometric dual records which faces of the original drawing lie on the two sides of each edge. The key point here is that a dual is itself an embedded graph: the way its edges are drawn carries information that its abstract vertex and edge sets do not.
We consider finite connected plane graphs. The original graph is simple unless stated otherwise, but its dual may have parallel edges or loops. For an edge whose two sides lie in the same face, the corresponding dual edge is a loop. If two faces share more than one edge, the dual has a separate edge for each such edge.
Choices of exact locations and curves are not important: they can be varied within the faces while preserving the embedded structure. An embedded isomorphism identifies vertices, edges and incidences in a way that a homeomorphism of the sphere carries one drawing to the other. It preserves the embedding, not just the abstract adjacency relation.
Why the Second Dual Recovers the First Drawing
The construction can be understood by looking locally around vertices, edges and faces. A dual vertex is placed inside each original face. Each dual edge crosses one original edge, and no other original edge. When the dual is drawn, its faces surround the original vertices: moving around one original vertex, the incident edge-ends occur in a cyclic order, and the dual edges crossing those edge-ends bound the corresponding dual face. If a vertex is a cut vertex, its face boundary may pass it more than once; those passages still belong to the same dual face associated with that vertex.
One way to organize this local picture is to mark a point in every face and a midpoint on every edge. Within each face, join its marked point to the midpoints of its boundary-edge occurrences without crossings. The resulting dual edges, joined across each edge midpoint, make the dual drawing. The remaining regions surround the original vertices. This construction also works when an edge is a bridge: its two sides belong to the same face, so its dual is a loop. If the graph is the single isolated vertex, there is one face and no edges; its dual is also a single isolated vertex, and the same correspondence holds.
Proof. Suppose first that \(G\) has at least one edge. In the chosen embedding of \(G^*\), the regions of the complement correspond one-to-one with the vertices of \(G\): the region associated with \(v\) is the dual face surrounding \(v\), as described by the local construction. Therefore the vertices of \((G^*)^*\), which represent faces of \(G^*\), correspond one-to-one with \(V(G)\).
For each original edge \(e\), the dual edge \(e^*\) crosses \(e\). The edge of \((G^*)^*\) corresponding to \(e^*\) crosses \(e^*\). It can therefore be drawn through the crossing point of \(e\) and \(e^*\), following the position of \(e\) on the sphere. Thus it has the same endpoints as \(e\): those endpoints are the two double-dual faces surrounding the original endpoints of \(e\). This gives a one-to-one correspondence between original and double-dual edges that preserves incidence and the cyclic arrangement of the drawing. Hence the correspondence is an embedded isomorphism.
If \(G\) has no edges, connectedness implies that it has exactly one vertex. Its complement on the sphere has one face. The dual has one vertex and no edges, and its dual also has one vertex and no edges. The correspondence is again an embedded isomorphism. \(\square\)
The theorem concerns the dual of the embedded graph, not merely its abstract graph. The drawing tells us which regions are faces, which sides of an edge belong to which faces, and how the dual edges are arranged around one another. Forgetting that drawing can erase information needed to reconstruct the original.
Worked Double-Dual Constructions
Worked Example: The Dual of a Plane Triangle
Let \(G\) have \(V(G)=\{a,b,c\}\) and \(E(G)=\{ab,bc,ca\}\), drawn as a triangle on the sphere. It has two faces, the inside and the outside, so \(G^*\) has vertices \(x\) and \(y\), representing those faces.
Each of the three original edges has the inside on one side and the outside on the other. Consequently, \(G^*\) has three parallel edges \(e_{ab}^*,e_{bc}^*,e_{ca}^*\), each joining \(x\) to \(y\). The embedding places these edges in the three separate positions corresponding to the original edges; they are not merged into one edge.
The three regions of this embedded dual correspond to \(a,b,c\). Thus \((G^*)^*\) has vertices \(f_a,f_b,f_c\). The edge crossing \(e_{ab}^*\) joins \(f_a\) to \(f_b\); the edges crossing \(e_{bc}^*\) and \(e_{ca}^*\) join \(f_b\) to \(f_c\) and \(f_c\) to \(f_a\), respectively. The result is a triangle with the original incidence pattern.
Check: \(G\) has \(3\) vertices, \(3\) edges and \(2\) faces. Its dual has \(2\) vertices and \(3\) edges, and the double dual has \(3\) vertices and \(3\) edges. The edge-by-edge correspondence above verifies the endpoints as well as the counts.
Worked Example: A Bridge Becomes a Dual Loop
Let \(G\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,ca,cd\}\). Draw the triangle \(abc\) and attach \(d\) to \(c\) by the edge \(cd\). The edge \(cd\) is a bridge, and both its sides belong to the outside face. The graph has an inside face \(F_1\) and an outside face \(F_0\).
Thus \(G^*\) has vertices \(x_0,x_1\), representing \(F_0,F_1\). Each of \(ab,bc,ca\) separates these two faces, so they produce three parallel edges between \(x_0\) and \(x_1\). The bridge \(cd\) has the same face on both sides, so it produces a loop at \(x_0\). The dual has \(2\) vertices and \(4\) edges: \(3\) parallel edges and \(1\) loop.
The embedded dual has four faces, corresponding to the original vertices \(a,b,c,d\). In its double dual, the edge crossing the dual edge for \(ab\) joins the faces corresponding to \(a\) and \(b\), and likewise for \(bc\) and \(ca\). The edge crossing the loop for \(cd\) joins the faces corresponding to \(c\) and \(d\). The loop’s two sides border different dual faces, so its double-dual edge is not a loop.
Check: The original has \(4\) vertices, \(4\) edges and \(2\) faces. The dual has \(2\) vertices and \(4\) edges; on the sphere its number of faces is \(4-2+2=4\), matching the original vertex count. The recovered edges are exactly \(ab,bc,ca,cd\), including the bridge \(cd\).
Worked Example: The Abstract Dual Does Not Determine the Original
Compare two plane trees. Let \(T_1\) have \(V(T_1)=\{1,2,3,4\}\) and \(E(T_1)=\{12,23,34\}\), a path. Let \(T_2\) have \(V(T_2)=\{1,2,3,4\}\) and \(E(T_2)=\{12,13,14\}\), a star. Each is connected, has \(4\) vertices and \(3\) edges, and has one face.
In either dual, the single original face gives one dual vertex. Each of the three original edges is a bridge, so each gives a loop at that dual vertex. Therefore the two abstract dual graphs are identical: one vertex with three loops. But \(T_1\) has degree sequence \(1,2,2,1\), while \(T_2\) has degree sequence \(3,1,1,1\). Their original graphs are not isomorphic.
The distinction is the embedding of the three loops. The regions between them in the embedded dual record the original vertices and their arrangement. With that embedding retained, taking the dual again recovers the path in the first case and the star in the second. With only the abstract one-vertex, three-loop graph, that distinction is absent.
Check: Both trees have \(3\) edges, so each dual has \(3\) loops; each tree has \(4\) vertices, so each embedded dual has \(4\) faces. The different degree sequences confirm that the original abstract graphs differ even though their abstract duals agree.
What Can Be Lost When the Drawing Is Forgotten?
Three pieces of information are particularly important in a dual construction:
- which faces lie on the two sides of each edge;
- which dual edge corresponds to each original edge, including separate edges that are parallel in the dual;
- the way dual edges are arranged in the embedding, which determines the dual faces.
The double-dual theorem uses all three. A common mistake is to simplify the dual by merging parallel edges or deleting loops, then expect a second dual to recover the original. For the triangle example, merging its three parallel dual edges into one would discard two edge correspondences. It would no longer be the geometric dual defined here, so the double-dual theorem would not apply.
Another frequent error is to assume that every dual edge joins two different dual vertices. The bridge example shows why that fails: the two sides of a bridge belong to the same face, so its dual edge is a loop. This is not a defect in the construction. The loop still has two sides in its embedding, and those sides are essential to recovering the original edge.
In short, an embedded dual retains enough information to recover the original plane graph, including its embedding. The abstract dual may retain less: even the underlying graph can be ambiguous, as the path and star examples show. The double-dual statement is therefore a claim about geometric duality, not an assertion that abstract adjacency alone always encodes a plane drawing.
Check Your Understanding
Use the distinction between abstract and embedded duals in your answers.
- Why does a bridge of a connected plane graph give a loop in its dual?
- For a plane cycle \(C_4\), describe the vertices and edges of its geometric dual.
- Explain which information about the triangle is lost if the three parallel edges in its dual are merged.
- Why can the double-dual theorem still apply when the original graph has a bridge?
- What feature of the embedded dual distinguishes the path and star in the third worked example?