Minimum Spanning Trees and Algorithms

We argue by an exchange argument, a standard technique for greedy-algorithm correctness proofs. Let $T$ be any MST of $G$, and suppose for contradiction that $e^* \notin T$. Write $e^* = \{u,v\}$ with $u \in S$, $v \in V \setminus S$. Since $T$ is a spanning tree, it is connected, so there is a unique path $P$ in $T$ from $u$ to $v$. Because $u \in S$ and $v \notin S$, the path $P$ must cross the cut $(S, V\setminus S)$ at least once: formally, walking along $P$ from $u$ to $v$, consider the first edge $f$ of $P$ whose far endpoint leaves $S$. Then $f = \{x,y\}$ with $x \in S$ and $y \in V\setminus S$, so $f$ is also a cut edge for $(S,V\setminus S)$. Because all weights are distinct and $e^*$ is the minimum-weight cut edge, we have $w(f) > w(e^*)$ (note $f \ne e^*$ since $e^* \notin T$ but $f \in T$). Form $T' = (T \setminus \{f\}) \cup \{e^*\}$. We check $T'$ is a spanning tree:

• Removing $f$ from the tree $T$ disconnects it into exactly two components, one containing $x$ (call it $C_x$) and one containing $y$ (call it $C_y$), because $T$ is a tree and removing any single edge from a tree splits it into exactly two components (a basic fact about trees, since a tree has a unique path between any two vertices, and deleting an edge on the unique $x$–$y$ path severs the only connection).
• Adding $e^* = \{u,v\}$ reconnects these two components, provided $u \in C_x$ and $v \in C_y$ (or vice versa). Indeed $u \in S$: is $u \in C_x$? Since $f$ was chosen as the first cut-crossing edge along $P$ from $u$, the sub-path of $P$ from $u$ to $x$ lies entirely within $S$ and entirely within $T$, so $u$ and $x$ are connected in $T \setminus \{f\}$, i.e. $u \in C_x$. Similarly the remainder of $P$ from $y$ to $v$ lies in $T\setminus\{f\}$ and shows $v \in C_y$.
• Hence $T'$ has $|V|-1$ edges (one removed, one added) and is connected (the two components are reunited by $e^*$), so $T'$ is a spanning tree.

Now compare weights:

since $w(e^*) < w(f)$. This contradicts the assumption that $T$ is a minimum spanning tree. Therefore $e^* \in T$ for every MST $T$. $\blacksquare$

Identical exchange argument, with one adjustment: we only need $w(f) \ge w(e^*)$, which still gives $w(T') \le w(T)$, so $T'$ is also an MST (not strictly better, but not worse), and it contains $e^*$. Start from any MST $T$; if it already contains $e^*$ we are done, otherwise the construction above produces an MST $T'$ containing $e^*$. $\blacksquare$

Suppose toward contradiction some MST $T$ contains $f = \{x,y\}$. Removing $f$ from $T$ splits $T$ into two components $C_x \ni x$ and $C_y \ni y$, exactly as in the previous proof. Since $f$ lies on the cycle $C$, the rest of $C$ (i.e. $C$ with $f$ removed) is an $x$–$y$ path in $G$ using only edges of $C \setminus \{f\}$; this path must cross from $C_x$ to $C_y$ at least once, so it contains some edge $g \ne f$ with one endpoint in $C_x$ and one in $C_y$. Since $f$ was the maximum-weight edge of $C$, $w(g) < w(f)$ (using distinctness; in the general case $w(g) \le w(f)$ with $T'$ below at least as good). Form $T' = (T \setminus \{f\}) \cup \{g\}$; by the same component-reunification argument as before, $T'$ is a spanning tree, and

contradicting minimality of $T$. Hence $f$ is in no MST. $\blacksquare$

We use induction combined with the Cut Property (an exchange/greedy-stays-ahead argument).

Step 1: $T$ is a spanning tree. By construction $T$ is acyclic at every stage, so the final $T$ is a forest. We must show $T$ is connected, i.e., spans all of $V$. Suppose not: then $T$ has more than one component, so some component $S \subsetneq V$ (nonempty) has no edge of $T$ leaving it. Since $G$ is connected, some edge $e = \{u,v\} \in E$ with $u \in S, v \notin S$ exists. Consider the first time this edge $e$ was examined by the algorithm (it is some $e_i$). At that moment, adding $e$ to the current forest could not create a cycle, because $u$ and $v$ lie in different components of $T$ at the end of the algorithm, hence also at every earlier stage (components of the growing forest only merge, never split, as edges are added). So the algorithm must have added $e_i$ — contradicting the assumption that no edge of $T$ leaves $S$. Hence $T$ is connected, and being acyclic and connected it is a spanning tree; a spanning tree on $n$ vertices always has $n-1$ edges (a known fact from the theory of Spanning Trees).

Step 2: $T$ is minimum. We prove more precisely that every edge $e_i$ added to $T$ is justified by the Cut Property. When the algorithm considers $e_i = \{u,v\}$ and decides to add it (because $u,v$ lie in different components of the current forest $T_i$, the forest built so far), let $S$ be the vertex set of the component of $T_i$ containing $u$. Then $e_i$ crosses the cut $(S, V\setminus S)$. Claim: $e_i$ is a minimum-weight edge crossing this cut. Suppose some edge $e_j = \{p,q\}$ with $p \in S, q \notin S$ had $w(e_j) < w(e_i)$. Since edges are processed in nondecreasing weight order, $e_j$ was considered before $e_i$ (as $j < i$, since weights are sorted and $w(e_j)<w(e_i)$ forces $j<i$, using the sorted indexing; ties are broken consistently by the fixed order $e_1,\dots,e_m$). At the time $e_j$ was considered, the forest built so far was a subforest of $T_i$ (edges only accumulate), so $p$ and $q$ were still in different components at that time — because $S$ is a union of components of every earlier sub-forest $T_k$ for $k \le i$ (components only merge as the algorithm proceeds, and $S$ is exactly the component of $u$ at stage $i$, hence at stage $j<i$, $u$'s component was a subset of $S$, and similarly the rest of $S$ was not yet merged with $V\setminus S$). Hence adding $e_j$ at that time would not have created a cycle, so the algorithm would have added $e_j$. But then at stage $i$, $u$ and $v$ would already be connected via $e_j$'s effect on components, contradicting that $u,v$ are in different components at stage $i$. This contradiction proves the claim: $e_i$ is a minimum-weight cut edge for $(S, V \setminus S)$. By the Cut Property (general-weight corollary), there exists an MST containing $e_i$. We now finish by a standard "stays ahead" induction: let $T^*$ be an MST maximizing the number of initial edges $e_1, \ldots, e_i$ (in Kruskal's chosen order) it shares with $T$; we show $T^* = T$. Suppose $T^*\ne T$. Let $e_i$ be the first edge (in the fixed order) where $T$ and $T^*$ differ, i.e. $e_i\in T\setminus T^*$ but $e_1,\dots,e_{i-1}$ agree on membership in both. By the cut argument above, $e_i$ is a minimum-weight edge crossing the cut $(S,V\setminus S)$ determined by the component structure built from $e_1,\ldots,e_{i-1}$. Since $T^*$ is a spanning tree, it must also cross this cut somewhere (as $u\in S,v\notin S$ must be connected in $T^*$); let $e_j$, $j > i$ necessarily by minimality of the weight-order and the "first difference" choice, be an edge of $T^*$ crossing this same cut with $w(e_j)\ge w(e_i)$ (since $e_i$ is minimum over this cut). Replacing $e_j$ by $e_i$ in $T^*$ — the same reunification argument as in the Cut Property proof — yields another spanning tree $T^{\*\*}$ with $w(T^{\*\*}) \le w(T^*)$, hence also an MST, but now agreeing with $T$ on one more initial edge than $T^*$ did. This contradicts maximality of the agreement count for $T^*$. Hence no difference exists, so $T = T^*$, and $T$ is a minimum spanning tree. $\blacksquare$

This is a direct application of the Cut Property, by induction on $k$.

Well-defined ness. As long as $V(T_k) \ne V$, since $G$ is connected there is at least one edge crossing the cut $(V(T_k), V\setminus V(T_k))$ (otherwise $G$ would be disconnected, a contradiction), so a minimum-weight such edge exists and $T_{k+1}$ can be formed. Each $T_k$ is a tree: $T_1$ trivially is, and inductively, adding an edge from a new vertex to an existing tree preserves the tree property (it adds one vertex and one edge, cannot create a cycle since the new vertex had no prior edges in $T_k$, and preserves connectivity).

Inductive claim. There exists an MST $T^*$ of $G$ with $T_k \subseteq T^*$ for every $k = 1, \ldots, n$. Base case $k=1$: $T_1 = (\{r\}, \emptyset)$ is a sub(forest) of every spanning tree, in particular of any MST $T^*$. Inductive step: suppose $T_k \subseteq T^*$ for some MST $T^*$. Let $e$ be the edge added to form $T_{k+1}$, a minimum-weight edge crossing the cut $(V(T_k), V\setminus V(T_k))$. If $e \in T^*$ already, then $T_{k+1} = T_k \cup \{e\} \subseteq T^*$ and we are done with the same $T^*$. If $e \notin T^*$: apply the Cut Property (general-weight corollary) to the cut $(V(T_k), V \setminus V(T_k))$: there is an MST $\widehat{T}$ containing $e$. We must further arrange $T_k \subseteq \widehat{T}$. Use the exact exchange construction from the Cut Property proof, applied starting from $T^*$ itself: since $e$ is a minimum-weight edge across the cut and $T^*$ is a spanning tree, $T^*$ contains some edge $f$ crossing the same cut (as argued in the Cut Property proof) with $w(f) \ge w(e)$; moreover $f \notin T_k$ because $T_k$'s edges do not cross this cut (all of $T_k$'s vertices are on one side by definition of the cut). Set $T^{\*\*} = (T^* \setminus \{f\}) \cup \{e\}$; by the reunification argument, $T^{\*\*}$ is a spanning tree with $w(T^{\*\*}) = w(T^*) - w(f) + w(e) \le w(T^*)$, hence $T^{\*\*}$ is also an MST. Since $f \notin T_k$, we have $T_k \subseteq T^* \setminus \{f\} \subseteq T^{\*\*}$, and $e \in T^{\*\*}$, so $T_{k+1} = T_k \cup \{e\} \subseteq T^{\*\*}$. Take the new MST to be $T^{\*\*}$. By induction, $T_n \subseteq T^*$ for some MST $T^*$. But $T_n$ is itself a spanning tree (it has $n$ vertices, is connected and acyclic by the well-definedness argument above), and any spanning tree contained in another spanning tree must equal it (both have exactly $n-1$ edges). Hence $T_n = T^*$, an MST. $\blacksquare$