Edge Exchange In Spanning Trees

Adding an Edge to a Spanning Tree

A spanning tree records enough edges to connect all the vertices of a connected graph, without containing a cycle. If an edge of the graph has been left out of the tree, adding it creates a cycle. The key point is that this cycle is unique, and any one of its edges can be removed to restore a spanning tree. This local exchange is useful for understanding how spanning trees relate to one another.

Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated first and last vertex, are distinct. A tree is a connected graph with no cycle. A spanning tree of a graph \(G\) is a subgraph with vertex set \(V(G)\) that is a tree.

The assumptions matter: \(G\) must have a spanning tree \(T\), and \(e\) must be an edge of \(G\) that is not already in \(T\). If \(G\) is connected, it has a spanning tree; if \(G\) has just one vertex and no loops, there is no edge \(e\) to add. The edge-exchange statement concerns a non-tree edge only when one exists.

Why the Added Edge Makes One Cycle

Proof. Let \(T\) be a tree and let \(u,v\) be distinct vertices. Since \(T\) is connected, there is at least one \(u\)-\(v\) path. Suppose there are two distinct such paths. Starting from \(u\), follow them until they first diverge; then follow one of the paths until it first meets the other path again. The two different segments between the divergence vertex and this first meeting vertex have no common internal vertex. Their union is a cycle, contradicting that \(T\) has no cycles. Thus there is exactly one \(u\)-\(v\) path. \(\square\)

Proof. The vertices \(u\) and \(v\) are distinct because \(G\) is simple. By the Lemma, there is exactly one \(u\)-\(v\) path in \(T\). Adding \(e=uv\) to that path forms a cycle. Any cycle in \(T+e\) must use \(e\), because \(T\) has no cycles. Removing \(e\) from any such cycle would leave a \(u\)-\(v\) path in \(T\). The uniqueness of that path shows that the cycle already constructed is the only one.

Now let \(f\) be any edge of this cycle. The graph \(T+e-f\) contains every vertex of \(T\). To show it is connected, take any two vertices \(x,y\). Their path in \(T\) either avoids \(f\), in which case it is still present, or uses \(f\). In the latter case, replace \(f\) in that path by the rest of the unique cycle, which joins the endpoints of \(f\) without using \(f\). This gives an \(x\)-\(y\) walk in \(T+e-f\), so \(x\) and \(y\) remain connected. Finally, \(T+e-f\) has no cycle: any cycle in it would also be a cycle in \(T+e\), whose unique cycle contains \(f\), but \(f\) has been removed. Thus \(T+e-f\) is connected and acyclic, so it is a tree on all the vertices of \(G\), hence a spanning tree. \(\square\)

The choice of \(f\) is restricted to the fundamental cycle. An edge of \(T\) outside that cycle cannot be removed in this exchange: the cycle remains, and the result is not a tree. This distinction is important when using the theorem to modify a spanning tree.

Tracing the Exchange

Which Removals Work?

The theorem gives a sufficient condition, and in this setting it also identifies exactly which edges can be removed while retaining a spanning tree.

Proof. If \(f\) is on the fundamental cycle, the theorem says that \(T+e-f\) is a spanning tree. Conversely, suppose \(f\) is not on the fundamental cycle. Then none of the edges of that cycle has been removed from \(T+e\), so the cycle is still present in \(T+e-f\). A graph containing a cycle is not a tree. Therefore \(T+e-f\) is not a spanning tree. \(\square\)

This “if and only if” can prevent a common error: it is not enough to add one edge and remove just any other edge. The removed edge must lie on the cycle created by the addition.

Moving Between Spanning Trees

The preceding example illustrates a general consequence: one spanning tree can be changed toward another by a valid edge exchange. The proof relies only on the unique-cycle property.

Proof. Since the trees differ, choose an edge \(e\in E(T_2)\setminus E(T_1)\). Adding \(e\) to \(T_1\) creates a unique cycle. The cycle cannot consist entirely of edges of \(T_2\): it contains \(e\), and \(T_2\) also contains \(e\), so if every other cycle edge were in \(T_2\), then \(T_2\) would contain a cycle, contradicting that it is a tree. Thus some edge \(f\) on the cycle is not in \(T_2\). Because every edge on the cycle other than \(e\) belongs to \(T_1\), this \(f\) lies in \(E(T_1)\setminus E(T_2)\). The edge-exchange theorem shows that \(T_1+e-f\) is a spanning tree. The exchange adds the edge \(e\), which was in \(T_2\), and removes \(f\), which was not in \(T_2\). Hence the number of shared edges increases by exactly one. \(\square\)

Repeated exchanges can therefore transform \(T_1\) into \(T_2\): as long as the trees differ, the proposition supplies an exchange that increases the shared-edge count. This process must stop, because a spanning tree has finitely many edges and the shared-edge count increases at each step. When the count equals the number of edges in either tree, all edges agree. This explains why local exchanges are a useful way to compare spanning trees, without having to construct an entirely new tree at once.

Common Pitfalls

Removing an edge outside the cycle. In the second example, the cycle after adding \(35\) is \(3,2,4,5,3\). A mistaken exchange might remove \(12\), reasoning that one edge was added and one was removed. But \(12\) is not on the cycle, so the cycle remains. The resulting graph cannot be a tree. The correction is to identify the fundamental cycle first and remove an edge on it.

Assuming there are several cycles. A tree has exactly one path between the endpoints of the added edge. Any cycle created by adding that edge must consist of the added edge and a path between its endpoints in the original tree. Since that path is unique, so is the cycle.

Forgetting the spanning condition. A cycle-edge removal must leave all original vertices in the graph. The operation \(T+e-f\) changes edges, not vertices, so it retains the full vertex set. The proof establishes both connectedness and absence of cycles; checking only one of these properties would not be enough to conclude that the result is a spanning tree.