Cycles and Cuts Across Planar Duals

Cycles and Bonds in a Plane Dual

A plane graph divides the plane into faces, and its dual records which faces lie on opposite sides of each primal edge. This makes it possible to translate a geometric separation into a statement about edges of the dual. The precise relationship is that a cycle in a connected plane graph corresponds to a bond in its dual, and every bond in the dual comes from a cycle in the plane graph.

Throughout, \(G\) is a finite connected plane graph and \(G^*\) is its plane dual. Each face of \(G\) gives a vertex of \(G^*\), and each edge \(e\) of \(G\) gives a corresponding dual edge \(e^*\) joining the faces on the two sides of \(e\). The dual may have parallel edges or loops, even when \(G\) is simple. A cycle in a simple graph has distinct vertices apart from its repeated start and end. When discussing a multigraph, we also allow a loop as a cycle of length \(1\) and two parallel edges as a cycle of length \(2\).

For a connected graph \(H\), a nonempty cut \(\delta_H(S)\) is a bond exactly when both induced subgraphs \(H[S]\) and \(H[V(H)\setminus S]\) are connected. Indeed, if both sides are connected, restoring any one edge of the cut after deleting the whole cut joins the sides, so no proper subset of the cut disconnects \(H\). Conversely, if one side is disconnected, take one of its connected components \(A\). Since \(H\) is connected, \(\delta_H(A)\) is nonempty; it is a proper subset of \(\delta_H(S)\), so the original cut is not minimal.

A Cycle Gives a Bond in the Dual

Proof. Regard the embedded cycle \(C\) as a simple closed curve. By the Jordan curve theorem, it has a bounded side and an unbounded side. Let \(S\) be the set of dual vertices corresponding to faces lying on the bounded side. Every face lies on one side or the other: a face cannot cross an edge of \(C\), which is part of the embedded graph.

An edge of \(C\) has one incident face on each side, so its dual edge crosses from \(S\) to \(V(G^*)\setminus S\). An edge not in \(C\) has its interior entirely on one side of \(C\); its two incident faces are therefore on that same side. Thus the dual edges corresponding to \(C\) are exactly \(\delta_{G^*}(S)\).

It remains to show that both sides of this cut are connected in the dual. Take any two faces on the bounded side and choose a point in the interior of each. Join the points by a curve lying inside that side, avoiding the finitely many graph vertices and crossing graph edges only at interior points. Such a curve can be chosen by a small perturbation of a path in the open region. As it passes from face to face, it crosses edges not in \(C\), so the corresponding dual vertices are joined by a walk using no dual edge of \(\delta_{G^*}(S)\). Hence the dual vertices in \(S\) are connected after the cut edges are removed. The same argument in the unbounded side connects all the dual vertices outside \(S\). The cut is nonempty, and both sides are connected; therefore it is a bond. \(\square\)

The proof also explains the geometric content: the cycle separates the faces into two groups, and its edges are exactly the edges through which the dual passes from one group to the other.

A Bond in the Dual Gives a Cycle

For the converse, we use a local property at each primal vertex. As one goes around a vertex of a plane graph, the incident face sectors occur in a cyclic order. Mark each sector according to whether its dual vertex belongs to \(S\) or to \(V(G^*)\setminus S\). An incident primal edge belongs to the edge set corresponding to \(\delta_{G^*}(S)\) exactly when the marks on its two sides differ. In a cyclic sequence of two kinds of marks, the number of changes is even: every change from the first kind to the second must eventually be matched by a change back. Consequently, every primal vertex has even degree in the subgraph formed by the edges corresponding to the cut. A loop contributes two to degree, in accordance with the usual degree convention.

Proof. Since \(B^*\) is a bond, it is a nonempty cut \(\delta_{G^*}(S)\) for some nonempty proper set \(S\) of dual vertices. Let \(B\) be the corresponding set of primal edges. The cyclic face-sector argument shows that every vertex has even degree in the subgraph with edge set \(B\).

Every nonempty finite graph in which all degrees are even contains a cycle. To see this, start along an edge and continue along unused edges for as long as possible. Whenever the walk reaches a vertex other than its starting vertex, the number of used incident edges there is odd, so the even total degree ensures that another unused incident edge is available. Finiteness forces a repeated vertex; the portion of the walk between two successive occurrences of a repeated vertex contains a cycle. This argument includes a loop or a pair of parallel edges when the graph is a multigraph. Apply it to \(B\) to obtain a cycle \(C\) whose edges form a nonempty subset of \(B\).

By the preceding theorem, the dual edges corresponding to \(C\) form a nonempty cut in \(G^*\). These dual edges are a subset of \(B^*\). Because \(B^*\) is a bond, no nonempty cut can be a proper subset of it. Therefore the dual edges corresponding to \(C\) are all of \(B^*\), and the primal edges of \(C\) are exactly \(B\). \(\square\)

Together, the two theorems give the cycle–bond correspondence: taking the duals of a cycle’s edges gives a bond, and taking the primal edges of a dual bond gives a cycle. The second proof uses minimality essentially. A general cut can correspond to more than one cycle.

Why a General Cut Need Not Be a Bond

Minimality cannot be omitted. A cut in the dual may correspond to a union of separate cycles in the plane graph. The following example also shows how a bridge becomes a loop in the dual without belonging to a cut.

Common Pitfalls and a Practical Test

A bond is not just any cut. For a cut in a connected graph, check that each side induces a connected subgraph. In the square example, deleting the four perimeter dual edges leaves the two interior faces connected by the diagonal, and the exterior face is the other connected side. That is why the cut is a bond. By contrast, in the two-triangle example, the side \(\{f_1,f_2\}\) is disconnected after the cut, so it is not a bond.

Do not confuse minimal with minimum. A bond is minimal under inclusion: no nonempty proper subset of it is a cut. This does not assert that it has minimum cardinality among all cuts. The cycle–bond correspondence uses inclusion-minimality, not a comparison of cut sizes.

Keep the edge correspondence explicit. The primal cycle’s edges correspond one-for-one to the dual bond’s edges. The vertices on each side of the dual cut are faces, not primal vertices. In examples, listing which faces each primal edge separates avoids mistaking an internal edge for a boundary edge.