[proofplan] We build a spanning tree from $G$ by iterated edge deletion. Starting with $G$ itself, we delete one edge at a time, always choosing an edge that lies on some cycle. Each deletion preserves connectivity (the deleted edge can be rerouted around the rest of the cycle, and the resulting walk yields an $x$–$y$ path by [Walk Contains Path](/theorems/2007)) and preserves the vertex set. The process terminates after at most $|E(G)|$ steps because the edge count strictly decreases. At termination, the graph has no cycle — otherwise we could delete another edge — so the final graph is connected and acyclic with the same vertex set as $G$. This is a spanning tree of $G$. [/proofplan] [step:Define the edge-deletion process] Let $G$ be a connected graph. We construct a finite sequence of spanning subgraphs $G_0, G_1, G_2, \ldots$ of $G$ by the following iterative rule. Set $G_0 := G$. Having defined $G_i$ with $V(G_i) = V(G)$, we form $G_{i+1}$ as follows: - If $G_i$ contains a cycle, pick any cycle $C_i$ of $G_i$, pick any edge $e_i \in E(C_i)$, and define $G_{i+1} := G_i - e_i$ (the graph with the same vertex set and one fewer edge). - If $G_i$ contains no cycle, stop and set $G^* := G_i$. We will show: (a) whenever the process runs the "delete-an-edge" branch, $G_{i+1}$ is connected, so the process preserves the invariant "$G_i$ is a connected spanning subgraph of $G$"; (b) the process terminates; (c) the terminal graph $G^*$ is a spanning tree of $G$. [/step] [step:Verify that deleting a cycle edge preserves connectivity] Suppose $G_i$ is a connected spanning subgraph of $G$ containing a cycle $C_i = v_0, v_1, \ldots, v_{r-1}, v_0$ with $r \ge 3$, and let $e_i \in E(C_i)$. Without loss of generality, reindex so $e_i = v_0 v_1$. Set $x := v_0$, $y := v_1$, $G_{i+1} := G_i - e_i$. We show $G_{i+1}$ is connected. Let $u, w \in V(G_{i+1}) = V(G_i)$. Since $G_i$ is connected, there is a $u$–$w$ walk $W$ in $G_i$. We construct from $W$ a $u$–$w$ walk $W^\star$ in $G_{i+1}$ as follows. Scan $W$ left to right; every time the walk traverses the edge $e_i = xy$ in either orientation, replace that single edge by the **rest-of-cycle arc** \begin{align*} A := y = v_1, v_2, \ldots, v_{r-1}, v_0 = x \qquad \text{(from } y \text{ to } x \text{),} \end{align*} or by its reverse $A^{\mathrm{rev}} = v_0, v_{r-1}, \ldots, v_1$ (from $x$ to $y$), matching the direction of the crossing. The edges of $A$ and $A^{\mathrm{rev}}$ are \begin{align*} v_1 v_2,\ v_2 v_3,\ \ldots,\ v_{r-1} v_0, \end{align*} all lying in $E(C_i) \setminus \{e_i\} \subseteq E(G_i) \setminus \{e_i\} = E(G_{i+1})$. The unaffected portions of $W$ use edges of $W$ other than $e_i$, which lie in $E(G_i) \setminus \{e_i\} = E(G_{i+1})$. Hence $W^\star$ is a $u$–$w$ walk in $G_{i+1}$. By [Walk Contains Path](/theorems/2007), if $u \neq w$ this walk contains a $u$–$w$ path in $G_{i+1}$; and if $u = w$ the walk of length $0$ already certifies connectivity directly. So for every $u, w \in V(G_{i+1})$ there is a $u$–$w$ walk in $G_{i+1}$, proving $G_{i+1}$ is connected. Also $V(G_{i+1}) = V(G_i) = V(G)$, so $G_{i+1}$ is a connected spanning subgraph of $G$. [guided] The claim is that deleting an edge from a cycle cannot disconnect a connected graph. The proof strategy is to fix any two vertices $u, w$ in the graph, take a walk between them in the original graph, and repair it: every time the walk uses the deleted edge, we detour around the rest of the cycle. Since the rest of the cycle is entirely made of edges other than the deleted one, the detoured walk lies entirely in the smaller graph. Formally: $G_i$ is connected and has a cycle $C_i = v_0, v_1, \ldots, v_{r-1}, v_0$ with $r \ge 3$. Pick an edge on $C_i$ to delete; re-indexing if necessary, call it $e_i = v_0 v_1$, and write $x := v_0$, $y := v_1$. Let $G_{i+1} := G_i - e_i$. We want to show: for every $u, w \in V(G_{i+1})$ there is a $u$–$w$ walk in $G_{i+1}$. Since $G_i$ is connected and $u, w \in V(G_{i+1}) = V(G_i)$, there is a $u$–$w$ walk $W$ in $G_i$. We transform $W$ to avoid using $e_i$. The detour is supplied by the rest of the cycle. The cycle $C_i$ consists of the edge $xy = e_i$ together with the "far side" \begin{align*} A : y = v_1 \to v_2 \to v_3 \to \cdots \to v_{r-1} \to v_0 = x, \end{align*} an arc from $y$ back to $x$. The edges of $A$ are $v_1 v_2, v_2 v_3, \ldots, v_{r-1} v_0$, which are edges of $C_i$ other than $e_i$ — none of them is $e_i = v_0 v_1$, as can be read off directly. Since $C_i$ is a cycle in $G_i$, these edges all lie in $E(G_i)$; and since none is $e_i$, they all survive in $E(G_{i+1})$. We also have the reverse arc $A^{\mathrm{rev}}$ from $x$ to $y$, which uses the same edges in the opposite order. Now transform $W$: scan left to right; whenever $W$ uses the edge $e_i$ in the direction $x \to y$, replace that single step by the arc $A^{\mathrm{rev}}$; whenever $W$ uses $e_i$ in the direction $y \to x$, replace that single step by $A$. The result $W^\star$ is a $u$–$w$ walk because (i) we substituted walks with the same endpoints, preserving the overall endpoints $u, w$, and (ii) every edge of $W^\star$ lies in $E(G_{i+1})$: edges inherited from $W$ (which were in $E(G_i) \setminus \{e_i\}$) are in $E(G_{i+1})$, and edges of the substituted arcs are in $E(G_{i+1})$ by the observation above. So $W^\star$ is a $u$–$w$ walk in $G_{i+1}$. To get a $u$–$w$ *path* if needed we could invoke [Walk Contains Path](/theorems/2007) — but the existence of a walk is already enough to conclude $u$ and $w$ are connected in $G_{i+1}$. Ranging over all $u, w$ shows $G_{i+1}$ is connected, and its vertex set is $V(G_i) = V(G)$, so it is a connected spanning subgraph of $G$. [/guided] [/step] [step:Prove termination of the process] The sequence $|E(G_0)|, |E(G_1)|, |E(G_2)|, \ldots$ strictly decreases: at each step where the "delete" branch runs, $|E(G_{i+1})| = |E(G_i)| - 1$. Since $|E(G_0)| = |E(G)|$ is finite (we work with finite graphs), the sequence hits $0$ after at most $|E(G)|$ steps. In fact the process stops earlier — as soon as $G_i$ has no cycle — but the point is only that it stops. Let $N$ be the smallest index for which $G_N$ has no cycle, and set $G^* := G_N$. [/step] [step:Conclude that $G^*$ is a spanning tree of $G$] We verify that $G^*$ is a spanning tree of $G$: 1. **Spanning.** At every step the vertex set was preserved: $V(G_{i+1}) = V(G_i) = V(G)$, so $V(G^*) = V(G)$. 2. **Subgraph of $G$.** At every step we only deleted edges: $E(G_{i+1}) \subseteq E(G_i) \subseteq E(G)$, so $E(G^*) \subseteq E(G)$. 3. **Connected.** By induction on $i$: $G_0 = G$ is connected by hypothesis; and the previous step showed that if $G_i$ is connected then $G_{i+1}$ is connected. Hence $G^* = G_N$ is connected. 4. **Acyclic.** By the termination condition, $G^*$ has no cycle. Since $G^*$ is connected and acyclic, it is a tree. Combined with (1) and (2), $G^*$ is a spanning tree of $G$. [/step] [step:Observation on maximal acyclicity] The construction actually shows more. At termination $G^*$ is connected, and any strict subgraph of $G^*$ obtained by further edge deletion from $G^*$ would be disconnected — this is minimal connectivity, equivalent to treeness by [Characterisations of Trees](/theorems/2008). We do not need this observation for the statement of the theorem, but it confirms that the constructed spanning tree is minimally connected, as expected. [/step]