Edges Can Change Their Role Under Duality
Passing from a plane graph to its dual exchanges vertices and faces: each primal face becomes a dual vertex, and each primal edge gives one dual edge between the faces on its two sides. This translation can change the apparent type of an edge. A bridge in the primal graph becomes a loop in the dual, while a loop in the primal becomes a bridge in the dual. Also, two different primal edges can give dual edges with the same pair of endpoints.
We work with finite, connected plane multigraphs. A multigraph may have loops and parallel edges; its embedding specifies where these edges lie. A bridge is an edge whose deletion increases the number of connected components. A loop has the same vertex at both ends. Parallel edges are distinct edges with the same two endpoints. The dual may itself have loops or parallel edges, even when a particular primal graph has neither.
The two sides of an edge mean the local regions on either side of its interior. They may belong to one face or to two different faces. The definition applies to loops and parallel edges as well: every primal edge has exactly one corresponding dual edge.
When Does an Edge Have the Same Face on Both Sides?
We first relate the two incident faces of a primal edge to whether that edge is a bridge. We use Euler’s formula for a plane graph with \(c\) connected components, in the form \(n-m+f=1+c\), where \(n\), \(m\), and \(f\) are its numbers of vertices, edges, and faces. This is the standard Euler formula for plane graphs; it applies to multigraphs, including graphs with loops and parallel edges.
Proof. Fix an edge \(e\) of a connected plane multigraph \(G\). Deleting the interior of \(e\) locally opens a passage between its two sides. If those sides were in distinct faces, this deletion merges those two faces; if they were in the same face, it does not merge two distinct faces. Thus the number of faces decreases by one exactly when the sides belong to distinct faces.
Write \(n=|V(G)|\), \(m=|E(G)|\), and let \(f\) be the number of faces. If \(e\) is a bridge, then \(G-e\) has \(n\) vertices, \(m-1\) edges, and \(c=2\) components. Euler’s formula gives its number of faces as \(1+2+(m-1)-n=m-n+2\). For \(G\), Euler’s formula gives \(f=1+1+m-n=m-n+2\). Therefore deleting \(e\) does not decrease the number of faces, so its two sides are in the same face.
If \(e\) is not a bridge, \(G-e\) is connected. Its number of faces, again by Euler’s formula, is \(1+1+(m-1)-n=m-n+1=f-1\). Deletion decreases the number of faces by one, so the two sides of \(e\) belong to distinct faces. These two cases prove both directions. \(\square\)
Primal Bridges Become Dual Loops
Proof. By the definition of the dual, \(e^*\) is a loop exactly when the two faces incident with \(e\) are the same. By the Lemma, this happens exactly when \(e\) is a bridge. \(\square\)
Worked Example: A Path Gives Dual Loops
Embed the path \(G\) with \(V(G)=\{a,b,c\}\) and \(E(G)=\{ab,bc\}\) in the plane, with no crossings. Its two edges are bridges: deleting \(ab\) separates \(a\) from \(b,c\), and deleting \(bc\) separates \(c\) from \(a,b\).
The embedding has one face, \(F\), since the drawing is a tree. Thus \(V(G^*)=\{F\}\). Each primal edge has \(F\) on both sides, so its dual edge is a loop at \(F\). The dual has two loops, one for \(ab\) and one for \(bc\).
Check: For the primal graph, \(n=3\), \(m=2\), and \(c=1\), so Euler’s formula gives \(f=1+1+2-3=1\). In the dual, removing either loop leaves the single vertex \(F\) connected; neither loop is a bridge. This confirms that the primal bridges correspond to dual loops, not to dual bridges.
Primal Loops Become Dual Bridges
The reverse correspondence involves connectivity in the dual. A loop in the primal is drawn as a closed curve through its vertex. In a plane embedding, that curve separates the two sides of the loop. A non-loop edge, by contrast, has distinct endpoints; the other edges around an endpoint provide a way to pass between the two sides of its dual edge without using that dual edge.
Proof. First suppose the primal edge \(e\) is a loop. Its drawing is a simple closed curve, so the Jordan curve theorem separates the plane into an inside and an outside. There are faces on both sides, namely the faces incident with the two local sides of \(e\). They are distinct. Every other primal edge lies on one side of the curve, apart from the shared vertex, and cannot cross the curve. Consequently, every dual edge other than \(e^*\) joins faces on the same side of the curve. In \(G^*-e^*\), there is no edge joining a dual vertex on one side to a dual vertex on the other. Both sides contain a dual vertex, so \(G^*-e^*\) is disconnected. Thus \(e^*\) is a bridge.
Now suppose \(e\) is not a primal loop, so its endpoints are distinct. If its two incident faces are the same, \(e^*\) is a loop and therefore is not a bridge: deleting a loop does not disconnect its vertex from any other vertex. If the incident faces are distinct, consider a small disk around one endpoint of \(e\). The incident edges meet the boundary of this disk in their circular order. Moving around the endpoint from one side of \(e\) to the other, without passing across \(e\), goes past the other incident edges. The dual edges corresponding to those other edges give a walk between the two faces that avoids \(e^*\). There is at least one such other incident edge: otherwise the endpoint has degree one and \(e\) is a bridge, in which case the Lemma already implies that its two sides are the same face. Thus when the incident faces are distinct, deleting \(e^*\) still leaves a route between its endpoints. In either case, \(e^*\) is not a bridge.
We have shown that a primal loop gives a dual bridge, and that a primal edge which is not a loop does not give a dual bridge. This proves both directions. \(\square\)
Worked Example: A Primal Loop Gives a Dual Bridge
Let \(G\) have \(V(G)=\{v\}\) and \(E(G)=\{\ell\}\), where \(\ell\) is a loop embedded as a circle based at \(v\). This is a connected plane multigraph. The loop separates an inside face \(F_{\mathrm{in}}\) from an outside face \(F_{\mathrm{out}}\).
The dual has \(V(G^*)=\{F_{\mathrm{in}},F_{\mathrm{out}}\}\) and one edge \(\ell^*\) joining these two vertices. Deleting \(\ell^*\) leaves two isolated vertices, so \(\ell^*\) is a bridge.
Check: The primal graph has \(n=1\), \(m=1\), and \(c=1\), giving \(f=1+1+1-1=2\), as found from the inside and outside faces. The dual has two vertices joined by one edge; its deletion increases the number of components from \(1\) to \(2\).
Distinct Edges Can Give Parallel Dual Edges
Two distinct primal edges produce parallel dual edges exactly when they have the same pair of incident faces. The pair is unordered: an edge does not distinguish a “first” face from a “second” one. If both sides of an edge are the same face, its dual edge is a loop instead. The edges in the dual retain their identities, so they are not merged merely because their endpoints agree.
Worked Example: Two Primal Edges Give Parallel Dual Edges
Let \(G\) have \(V(G)=\{a,b\}\) and two distinct parallel edges \(e_1,e_2\) joining \(a\) to \(b\). Embed the edges as two noncrossing arcs between \(a\) and \(b\), forming a bounded region between the arcs. Call that face \(F_{\mathrm{in}}\) and call the exterior face \(F_{\mathrm{out}}\).
Each primal edge has \(F_{\mathrm{in}}\) on one side and \(F_{\mathrm{out}}\) on the other. Therefore \(G^*\) has vertices \(F_{\mathrm{in}},F_{\mathrm{out}}\), with two distinct edges \(e_1^*,e_2^*\) joining them. These are parallel dual edges.
Check: The primal graph has \(n=2\), \(m=2\), and \(c=1\), so Euler’s formula gives \(f=1+1+2-2=2\), matching the two faces described. Deleting either primal edge leaves the other edge joining \(a\) and \(b\), so neither primal edge is a bridge; accordingly, neither dual edge is a loop. In the dual, deleting either of the two parallel edges still leaves the other joining the two face-vertices, so neither is a bridge. Counting directly, the dual has two vertices and two edges, exactly one for each primal edge.
Common Pitfall: Do Not Swap the Correspondences
A tempting but incorrect claim is that a primal bridge becomes a dual bridge. The path example disproves it: each primal edge is a bridge, but the dual consists of one vertex with two loops. The correct paired statements are primal bridge if and only if dual loop and primal loop if and only if dual bridge.
Another mistake is to assume parallel primal edges always produce parallel dual edges. The dual endpoints are determined by the incident faces, not by the primal endpoints. To decide whether two dual edges are parallel, check whether their primal edges have the same two incident faces. This is the relevant test, whether or not the primal edges themselves are parallel.
These correspondences are useful because they let us read structural information across an embedding. A dual loop signals a primal bridge; a dual bridge signals a primal loop; and repeated edges between a pair of dual vertices record repeated adjacencies between the same pair of primal faces.
Check Your Understanding
Use the definitions and the face incidences in each question to justify your answers.
- In a connected plane multigraph, what property of a primal edge is equivalent to its dual edge being a loop?
- Why does deleting a loop from a graph not make that graph more disconnected?
- Can two distinct primal edges give parallel dual edges if their pairs of incident faces differ?
- In the two-parallel-edge example, what happens to the connectivity of the dual if just one dual edge is deleted?
- Explain why a primal bridge does not correspond to a dual bridge in the embedded path example.