Spanning Trees

We prove each part in turn, using induction and direct combinatorial argument (no circular appeal to later machinery).

(1) Existence. Induct on $m$, the number of edges, for connected graphs on a fixed vertex set. If $G$ itself is acyclic, then a connected acyclic graph is by definition a tree Trees and Their Properties, so $T = G$ is a spanning tree. Otherwise $G$ contains a cycle $C$; let $e$ be any edge of $C$. We claim $G - e$ (delete $e$, keep all vertices) is still connected. Indeed, take any two vertices $u,w \in V$ and a walk between them in $G$; if the walk uses $e = xy$, replace that use of $e$ by the path $C - e$ from $x$ to $y$ (which exists since $C$ is a cycle and removing one edge from a cycle leaves a path connecting its endpoints); the resulting walk avoids $e$. Hence $G-e$ is connected, has the same vertex set $V$, and has $m-1$ edges. By the induction hypothesis (base case $m = n-1$ with $G$ already a tree, handled above), $G - e$ has a spanning tree, and this is also a spanning tree of $G$ since it uses only edges of $G$ and spans $V$. This completes the induction.

(2) Edge count. This is a direct restatement of the basic fact that a tree on $n$ vertices has exactly $n - 1$ edges Trees and Their Properties, applied to any spanning tree $T$, which is a tree with $|V(T)| = n$. Since $E_T \subseteq E$, we get $m = |E| \geq |E_T| = n - 1$.

(3) Fundamental cycles. Fix $e = uv \notin E_T$. Since $T$ is a tree, there is a unique $u$–$v$ path $P$ in $T$ (uniqueness of paths in trees is a basic property Trees and Their Properties); since $e \notin E_T$, $P$ does not use $e$, so $P$ together with $e$ forms a closed walk visiting each of its vertices once — a cycle $C_T(e) = P \cup \{e\}$, contained in $E_T \cup \{e\}$. Uniqueness of the cycle inside $E_T \cup \{e\}$: Suppose $C'$ is any cycle contained in $E_T \cup \{e\}$. If $C'$ used no edges outside $E_T$, then $C'$ would be a cycle inside the tree $T$, contradicting acyclicity of $T$. So $C'$ must use $e$ (the only edge of $E_T\cup\{e\}$ outside $E_T$). Removing $e$ from $C'$ leaves a $u$–$v$ path using only tree edges, i.e. a $u$–$v$ path in $T$. By uniqueness of paths in the tree $T$, this path equals $P$. Hence $C' = P \cup \{e\} = C_T(e)$, proving uniqueness. Uniqueness of the chord in $C_T(e)$: By construction, $C_T(e) \setminus \{e\} = P \subseteq E_T$, so $e$ is the only edge of $C_T(e)$ outside $E_T$, i.e. the only non-tree edge in the cycle.

(4) Fundamental cutsets. Fix $f \in E_T$. Since $T$ is a tree, $T - f$ (delete edge $f$, keep all vertices) is disconnected into exactly two components: removing any single edge from a tree always yields exactly two components, because a tree has $n-1$ edges and is minimally connected — deleting one edge lowers the edge count to $n - 2$, and a graph with $n$ vertices and $n-2$ edges that is a forest (subgraph of a tree, hence acyclic) with $c$ components satisfies $n - 2 = n - c$ (edge count of a forest Trees and Their Properties), forcing $c = 2$. Let $A, B$ be the vertex sets of these two components; $A, B$ partition $V$, both nonempty since $f$ had two distinct endpoints landing one in each part (the endpoints of $f$ are separated by its removal, as $f$ was the unique tree path between them). By definition, $D_T(f)$ is exactly the set of $G$-edges with one endpoint in $A$ and one in $B$. Minimality (disconnects $G$, and no proper subset does): Removing all of $D_T(f)$ from $G$ leaves no edges between $A$ and $B$, so $G - D_T(f)$ has no $A$–$B$ path, hence is disconnected (as $A,B$ are both nonempty). Now let $D' \subsetneq D_T(f)$ be any proper subset; we show $G - D'$ is still connected, establishing minimality. Since $D' \neq D_T(f)$, some edge $g \in D_T(f) \setminus D'$ survives in $G - D'$, and $g$ crosses from $A$ to $B$. Take any $x, y \in V$. If both lie in $A$: since $A$ is the vertex set of a connected component of $T - f$, there is a tree path between them entirely inside $A$, hence entirely surviving in $G - D'$ (tree edges within $A$ are not in $D_T(f)$, as they have both endpoints in $A$). Symmetric argument if both lie in $B$. If $x \in A, y \in B$, route $x$ to an endpoint of $g$ in $A$ via tree edges inside $A$, cross $g$, then route to $y$ inside $B$ via tree edges. In every case $G - D'$ has an $x$–$y$ walk, so $G-D'$ is connected. Hence $D_T(f)$ is a minimal disconnecting set — a genuine cutset. Uniqueness of the tree edge in $D_T(f)$: Any tree edge $f' \in E_T$ with $f' \in D_T(f)$ must cross from $A$ to $B$. But $A$ and $B$ are exactly the two components of $T - f$; the only tree edge crossing between them is $f$ itself, since all other tree edges lie within one component (they connect two vertices already joined by a path avoiding $f$, so both endpoints are in the same component of $T-f$). Hence $f' = f$, proving uniqueness. $\blacksquare$

($\Rightarrow$) If $(V,F)$ is a spanning tree it is by definition connected and acyclic; both directions are immediate. ($\Leftarrow$, connected case) Suppose $(V,F)$ is connected with $|F| = n - 1$. If $(V,F)$ had a cycle, deleting one edge of that cycle would keep it connected (same argument as in the Existence proof of the theorem) while leaving $n-2$ edges spanning $n$ vertices — but a connected graph on $n$ vertices needs at least $n-1$ edges (this follows by induction: a connected graph with $c$ components and $n$ vertices, viewed after removing edges from cycles repeatedly until acyclic, needs at least $n - c$ edges, and $c=1$ here forces at least $n-1$; formally this is the same edge-counting fact used for forests in part (2) of the theorem). This contradicts having only $n-2$ edges. So $(V,F)$ is acyclic, hence a tree, hence a spanning tree. ($\Leftarrow$, acyclic case) Suppose $(V,F)$ is acyclic with $|F| = n-1$ vertices. An acyclic graph is a forest, so if it had $c$ components its edge count equals $n - c$ (forest edge-count fact, Trees and Their Properties). Since $|F| = n - 1 = n - c$, we get $c = 1$, i.e. $(V,F)$ is connected. Hence it is connected and acyclic, i.e. a tree, hence a spanning tree. $\blacksquare$