Spanning Trees and Cotrees

From a Primal Tree to a Dual Tree

A spanning tree selects enough edges to connect all vertices of a graph without creating a cycle. In a plane graph, each edge also has a corresponding edge in the dual: its endpoints are the faces on the two sides of the primal edge. A striking fact is that the edges omitted from a primal spanning tree, rather than the edges it selects, form a spanning tree in the dual. This complement is called the cotree of the primal spanning tree.

We work with finite, connected, simple plane graphs. A plane graph is a graph together with a fixed embedding in the plane in which edges meet only at common endpoints. Its faces are the regions of the complement of the embedded graph, including the unbounded face. The dual may have parallel edges or loops, even when the plane graph is simple: two different primal edges may have the same pair of incident faces, and a primal bridge has the same face on both sides.

A tree is a connected graph with no cycles. For a multigraph, a loop is a cycle of length one and a pair of parallel edges forms a cycle of length two. A tree on one vertex and no edges is allowed. We will show that the cotree is a tree, including in the case where the primal graph itself is a tree.

Why the Cotree Is Connected

We use two elementary facts about plane graphs and finite graphs. First, the dual of a connected plane graph is connected. To see this, take points in any two faces and join them by a curve that avoids all vertices and crosses edges transversely, one at a time. Such a curve can be chosen by a small perturbation because the graph has finitely many vertices and edges. The sequence of faces visited by the curve gives a walk in the dual between the chosen faces.

Second, we need the following fact about edges that separate two groups of faces. The proof is included because the nonempty condition matters.

Proof. Start with an edge and extend a trail (a walk with no repeated edges) as long as possible in the graph. This process terminates because the graph has finitely many edges. If the trail ended at a vertex different from its starting vertex, the trail would use an odd number of edges incident with its endpoint: each visit along the trail pairs an arrival with a departure, leaving one unpaired arrival at the endpoint. Since the endpoint has even degree, at least one incident edge would then be unused, and the trail could be extended. This contradicts its maximality. The trail therefore ends where it started and is a nonempty closed trail. Choose a shortest nonempty closed segment of that trail. Its internal vertices cannot repeat, since a repetition would give a shorter nonempty closed segment. It is therefore a cycle; because the graph is simple, its length is at least three. \(\square\)

Now let \(H\) be the subgraph of \(G^*\) consisting of the cotree edges and all dual vertices. Suppose, for contradiction, that \(H\) is disconnected. Partition its vertices into a nonempty group \(A\) and its nonempty complement so that no edge of \(H\) joins the two groups. Since the full dual \(G^*\) is connected, at least one dual edge does join the groups. Let \(B\) be the set of primal edges whose duals join the groups. No such edge belongs to the cotree, so every edge of \(B\) belongs to \(T\).

At each primal vertex, consider the faces in the sectors around it, in their circular order, and mark each face according to whether its dual vertex is in \(A\) or outside \(A\). An incident primal edge belongs to \(B\) exactly when the marks on its two sides differ. In a circular sequence of two possible marks, the number of changes is even: every change from the first mark to the second must be balanced by a change back. Thus every primal vertex has even degree in the subgraph with edge set \(B\). Also \(B\) is nonempty. The lemma gives a cycle made of edges in \(B\), hence a cycle in \(T\). That contradicts the definition of a tree. Therefore \(H\), the cotree, is connected.

The Spanning-Tree/Cotree Theorem

For a connected plane graph, Euler’s formula states that \(n-m+f=2\), where \(n\) is the number of vertices, \(m\) the number of edges, and \(f\) the number of faces. We use Euler’s formula as the standard result established in the earlier material on planar graphs.

Proof. We have shown that the cotree is connected. A spanning tree on \(n\) vertices has \(n-1\) edges: one can construct it by starting at a vertex and repeatedly adding an edge to a vertex not yet reached, until every vertex is reached. Each added edge brings in exactly one new vertex. In the connected plane graph \(G\), therefore, \(|E(T)|=n-1\). Euler’s formula gives \(m-n+1=f-1\), so the cotree has \(|E(G)\setminus E(T)|=m-(n-1)=m-n+1=f-1\) edges and \(f\) vertices.

Finally, any connected graph on \(f\) vertices contains a spanning tree with \(f-1\) edges, by the same construction. Since the connected cotree itself has exactly \(f-1\) edges, it has no edges in addition to those of that spanning tree. Thus it is itself a tree. This includes \(f=1\), when a connected one-vertex graph with zero selected edges is a tree. \(\square\)

The theorem’s complement is essential: the primal tree edges do not generally give a dual tree. The cotree uses all faces as its vertices and selects precisely the dual edges of the primal edges not in \(T\).

Worked Plane-Graph Examples

Common Pitfall and Why the Correspondence Matters

Common mistake: dualizing the tree edges instead of taking their complement. In the triangle example, the chosen primal tree has edges \(12\) and \(23\). Its dual edges \(12^*\) and \(23^*\) are two parallel edges between \(f_0\) and \(f_1\). They connect the dual vertices, but together they form a cycle of length two, so they are not a dual tree. The correction is to omit those dual edges and select the dual of the remaining primal edge \(31\). That single edge is the cotree.

The correspondence is useful because it translates a choice in the primal graph into a complementary choice in the dual. For example, when an argument needs a connected, cycle-free set of dual edges, a primal spanning tree supplies one immediately: take the duals of exactly the edges not in that tree. The proof also explains why the two choices fit together: if the cotree failed to connect the faces, the primal edges crossing a partition of those faces would lie in the tree and would contain a cycle, which a tree cannot contain.

Keep the hypotheses in view. The theorem concerns a connected plane graph and its fixed embedding; the faces, and therefore the dual, depend on that embedding. The dual may have loops or parallel edges, and the cotree may have no edges when the primal graph is itself a tree. Neither feature invalidates the conclusion.