Extracting A Spanning Tree From A Connected Graph

Why Delete Edges to Find a Spanning Tree?

A connected graph can contain more edges than are needed to keep all its vertices connected. Edges on cycles are redundant in a specific sense: if one of them is removed, the rest of that cycle still provides a route between its endpoints. Repeating such deletions gives a direct existence proof and a practical method for extracting a spanning tree.

Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A graph is connected if every pair of distinct vertices is joined by a path. A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated start and finish, are distinct.

The method applies to a finite connected graph, which by convention here has at least one vertex. If it has just one vertex, it is already a tree: it is connected and has no cycles, so no deletion is needed. For a graph with more vertices, the procedure repeatedly finds a cycle in the graph currently under consideration and deletes one edge of that cycle. The word “currently” matters: after each deletion, the remaining graph may have different cycles from the original graph.

Why a Cycle Edge Can Be Deleted

Proof. Write \(e=uv\), and let \(C\) be a cycle containing \(e\). The other edges of \(C\) form a path from \(u\) to \(v\) that does not use \(e\). To show that \(G-e\) is connected, take any two distinct vertices \(x,y\). Since \(G\) is connected, choose an \(x\)-\(y\) path in \(G\). If it does not use \(e\), it remains a path in \(G-e\). If it does use \(e\), replace that occurrence of \(e\) by the \(u\)-\(v\) path in \(C-e\), using the appropriate direction along that path. This gives an \(x\)-to-\(y\) walk in \(G-e\). Removing any repeated portions of a walk produces a path with the same endpoints, so \(x\) and \(y\) are connected in \(G-e\). This holds for every pair, and hence \(G-e\) is connected. \(\square\)

The replacement argument explains exactly why the condition matters. An arbitrary edge need not have an alternative route between its endpoints. But an edge on a cycle always has one: the rest of the cycle.

The Cycle-Deletion Theorem

Proof. Let \(G_0=G\), where \(G\) is finite and connected. Whenever the current graph \(G_i\) has a cycle, choose any edge \(e_i\) on that cycle and define \(G_{i+1}=G_i-e_i\). By the Lemma, each \(G_{i+1}\) is connected. Deleting an edge does not delete a vertex, so every graph in the process has the original vertex set \(V(G)\).

If the initial graph has \(m=|E(G)|\) edges, each step reduces the number of edges by exactly one. Thus there can be at most \(m\) steps. When the procedure stops, the current graph has no cycle; otherwise another deletion would be possible. Its vertex set is still \(V(G)\), it is connected, and it has no cycles. By definition, it is a spanning tree of \(G\). If \(G\) has one vertex, the process has zero steps and the same conclusion holds. \(\square\)

This proof also justifies the method: connectivity is maintained at every step, and termination is guaranteed by finiteness. There is no requirement to choose a special cycle or a special edge of that cycle. The only condition on each choice is that the edge actually lies on a cycle in the current graph.

Worked Deletions

Common Pitfall: Deleting an Edge That Is No Longer on a Cycle

Consider the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\). Initially, \(12,23,31\) form a triangle. Delete \(12\). The current edge set is \(\{23,31,34\}\), which is the path \(2,3,1\) together with the edge \(34\), or equivalently the path \(2,3,1\) with \(4\) attached at \(3\). It has no cycle, so the procedure must stop.

A wrong continuation would be: “The original triangle also contained \(23\), so delete \(23\).” But the original triangle is no longer present. Deleting \(23\) now leaves \(2\) isolated from \(1,3,4\), so the graph is disconnected. The correction is to inspect cycles in the current graph before each deletion. The theorem guarantees connectivity only for an edge that lies on a cycle at that step.

What the Method Guarantees

Cycle deletion is an existence method, not a rule for choosing a unique answer. Different eligible choices can leave different sets of edges, but every final graph produced by the procedure has the same essential properties: it contains all original vertices, remains connected throughout, and stops only when it has no cycles. Together, those properties are exactly what make it a spanning tree.

Two checks are especially useful when carrying out the method by hand:

• Before deleting an edge, list or describe a cycle containing it in the current graph.
• After the last deletion, verify that every original vertex remains, that the result is connected, and that it contains no cycle.

An edge count can provide an additional consistency check, but by itself it cannot replace these structural checks. The argument works because of the cycle providing an alternate route, not merely because the number of edges decreases.