Verifying A Candidate Minimum Spanning Tree

Testing a Candidate Tree

A spanning tree is a compact way to connect every vertex of a graph without creating cycles. But a tree that spans the graph is not necessarily one of minimum total weight. When a candidate tree is already given, we can test whether it is minimum by checking the edges that the candidate leaves out. The key comparison is between the weight of each such edge and the heaviest edge on the tree path joining its endpoints.

Throughout, $G=(V,E)$ is a finite, connected, simple, undirected graph. Each edge $e\in E$ has a real weight $w(e)$. The weights need not be positive or distinct. A spanning tree $T$ is a subgraph that contains every vertex and is connected and acyclic. Its total weight is the sum of the weights of its edges. A minimum spanning tree (MST) is a spanning tree whose total weight is no greater than that of any other spanning tree of $G$.

In a tree, there is exactly one path between any two distinct vertices. For an edge $e=uv$ not in $T$, write $P_T(u,v)$ for that unique path. Since $u\ne v$, this path has at least one edge, so its maximum edge weight is defined. A candidate is checked against every edge in $E\setminus E(T)$, not against the edges it already contains.

Theorem: A spanning tree $T$ of a finite, connected, weighted graph $G$ is a minimum spanning tree if and only if, for every edge $uv\in E\setminus E(T)$, $$ w(uv)\ \ge\ \max\{w(f): f\in P_T(u,v)\}. $$ The inequality is non-strict: equality is allowed.

The condition compares an omitted edge with the maximum weight on its tree path. If an omitted edge is lighter than even one edge on that path, exchanging the two can improve the tree. Conversely, if no such improvement is possible on any path, exchanges can transform any competing spanning tree into the candidate without decreasing the total weight.

The Edge-Exchange Fact

Lemma: If $T$ is a tree and $e=uv$ is an edge whose endpoints are vertices of $T$ but $e\notin E(T)$, then adding $e$ to $T$ creates exactly one cycle. Removing any edge of that cycle produces a tree on the same vertices.

Proof. There is a unique $u$-$v$ path in $T$. Adding $e$ to that path makes a cycle. Any cycle in $T+e$ must contain $e$, since $T$ itself has no cycles; the remainder of such a cycle would be a $u$-$v$ path in $T$. The uniqueness of that path proves that the cycle is the only one. Now remove any edge $f$ of this cycle. The resulting graph has no cycle: any cycle remaining would also have been a cycle of $T+e$, and the only such cycle used $f$. It is connected as well. Removing $f$ breaks the cycle, but the rest of the cycle still provides a route between the endpoints of $f$; thus any route in $T+e$ that used $f$ can be rerouted around the rest of the cycle. The resulting graph is connected and acyclic, so it is a tree. $\square$

Why the Criterion Works

Proof of the theorem. First suppose that $T$ is an MST. Fix any edge $e=uv\in E\setminus E(T)$, and choose an edge $f$ of maximum weight on $P_T(u,v)$. By the lemma, adding $e$ to $T$ creates a cycle consisting of $e$ and $P_T(u,v)$; removing $f$ gives another spanning tree. If $w(e)<w(f)$, the new tree has total weight $w(T)+w(e)-w(f)<w(T)$, contradicting that $T$ is minimum. Therefore $w(e)\ge w(f)$, as required. This argument applies to each omitted edge.

For the reverse direction, suppose the stated inequality holds for every edge outside $T$. Let $S$ be any spanning tree of $G$. We show that $S$ can be changed into $T$ by exchanges that never increase total weight. If $S\ne T$, choose an edge $e=uv\in E(T)\setminus E(S)$. Removing $e$ from $T$ separates $T$ into two components, with vertex sets $A$ and $B$, where $u\in A$ and $v\in B$. Because $S$ is connected, its $u$-$v$ path crosses from $A$ to $B$. Choose an edge $f$ on that path that crosses this partition.

The only edge of $T$ crossing between $A$ and $B$ is $e$: any other such edge, together with paths within the two components, would create a cycle in $T$. As $e\notin E(S)$, the chosen edge $f$ is not in $T$. Its path in $T$ must cross from $A$ to $B$, so that path contains $e$. The assumed condition applied to $f$ therefore gives $$ w(f)\ \ge\ \max\{w(g):g\in P_T(f)\}\ \ge\ w(e), $$ where $P_T(f)$ denotes the tree path between the endpoints of $f$. Adding $e$ to $S$ and removing $f$ gives a spanning tree by the lemma, and its weight changes by $w(e)-w(f)\le 0$. It also contains one more edge of $T$ than $S$ did, and loses no edge of $T$, since $f\notin E(T)$.

Repeat this step whenever the current tree differs from $T$. Each step increases the number of edges shared with $T$, so after finitely many steps the current tree is $T$. Its weight has never increased. Thus $w(T)\le w(S)$. Since $S$ was any spanning tree, $T$ is an MST. If $T=S$ at the outset, the conclusion already holds. For a graph with one vertex, the spanning tree has no edges and there are no edges to test; it is the only spanning tree, so the criterion holds vacuously. $\square$

Applying the Test

Worked Example: A Candidate That Passes

Let $V=\{1,2,3,4\}$ and let the weighted edge set be $12:1,\ 23:4,\ 34:2,\ 13:5,\ 24:6,\ 14:7$, where $ij:x$ means that edge $ij$ has weight $x$. Take the candidate tree $T$ with edges $12,23,34$. It is a path through all four vertices, so it is a spanning tree.

Check the three omitted edges in turn. For $13$, the tree path is $1,2,3$, with edge weights $1,4$; the maximum is $\max(1,4)=4$, and $w(13)=5\ge4$. For $24$, the path is $2,3,4$, with weights $4,2$; the maximum is $\max(4,2)=4$, and $w(24)=6\ge4$. For $14$, the path is $1,2,3,4$, with weights $1,4,2$; the maximum is $\max(1,4,2)=4$, and $w(14)=7\ge4$.

Check: All omitted edges pass the criterion, so $T$ is an MST. Its weight is $1+4+2=7$. The three path maxima just used are $4,4,4$, and the corresponding comparisons are $5\ge4,\ 6\ge4,\ 7\ge4$; thus every omitted edge has been checked.

Worked Example: A Candidate That Fails

Let $V=\{1,2,3,4\}$ and let $E$ consist of $12:1,\ 23:5,\ 34:2,\ 14:4$. Consider the candidate $T$ with edges $12,23,34$. This is a spanning path. The only omitted edge is $14$; its path in $T$ is $1,2,3,4$, whose edge weights are $1,5,2$. The maximum is $\max(1,5,2)=5$, but $w(14)=4<5$. The criterion fails.

We can see the improvement directly. Add $14$, which closes the cycle $1,2,3,4,1$, and remove the heaviest path edge $23$, of weight $5$. The resulting edges $12,14,34$ form the spanning path $2,1,4,3$. The candidate’s weight is $1+5+2=8$; the exchanged tree’s weight is $1+4+2=7$. Hence the candidate is not minimum.

Check: The difference is $8-7=1$, and the exchange changes the weight by $w(14)-w(23)=4-5=-1$. Both calculations show a decrease of $1$.

Worked Example: Equality and Tied Weights

Let $V=\{1,2,3,4\}$ and let the weighted edges be $12:2,\ 23:3,\ 34:2,\ 14:3,\ 13:3$. Take $T$ to have edges $12,23,34$, a spanning path. For omitted edge $14$, the tree path has weights $2,3,2$, so its maximum is $\max(2,3,2)=3=w(14)$. For omitted edge $13$, the path has weights $2,3$, so its maximum is $\max(2,3)=3=w(13)$. Both comparisons hold with equality, so $T$ is an MST.

Equality need not mean that the candidate is the only MST. Add $14$ to $T$ and remove $23$ from the resulting cycle. The new edges $12,14,34$ form a spanning tree. The original tree has weight $2+3+2=7$, and the new tree has weight $2+3+2=7$.

Check: Both omitted edges have weight $3$, and their respective path maxima are $3$ and $3$. The alternative tree also has three edges and total weight $7$, confirming that the equality case is consistent with a tie.

A Practical Verification Procedure

For a proposed edge set, first confirm that it really is a spanning tree: it must use only edges of $G$, include every vertex, and be connected and acyclic. Then, for each edge of $G$ omitted from the candidate, find the unique path between its endpoints in the tree and compare the omitted edge’s weight with the largest weight on that path. The theorem says that the candidate is minimum precisely when every comparison passes.

The following table records the complete path-maximum test for the first example. It gives the omitted edges in turn, the path weights found in the candidate tree, the maximum on each path, and the comparison that determines the outcome.

Omitted edge	Tree-path weights	Path maximum	Comparison
13, weight 5	1, 4	max(1, 4) = 4	5 ≥ 4: pass
24, weight 6	4, 2	max(4, 2) = 4	6 ≥ 4: pass
14, weight 7	1, 4, 2	max(1, 4, 2) = 4	7 ≥ 4: pass

For a small graph, these paths can be found by inspection. For larger trees, one can preprocess the tree so that maximum-edge queries on paths can be answered efficiently; the mathematical test remains the same. This is a verification method: it does not require running a construction algorithm such as Kruskal’s or Prim’s.

Common Pitfall: Use the Maximum, Not Another Path Statistic

The criterion does not compare an omitted edge with the minimum edge on its tree path, nor with the sum of all path-edge weights. For example, let $V=\{1,2,3,4\}$, with weighted edges $12:1,\ 23:5,\ 34:2,\ 14:4$, and use the path $12,23,34$ as the candidate. A mistaken test that compares $w(14)=4$ only with the minimum path weight computes $\min(1,5,2)=1$ and concludes $4\ge1$, apparently accepting the candidate. But the required maximum is $\max(1,5,2)=5$, and $4<5$. Replacing edge $23$ of weight $5$ by edge $14$ of weight $4$ reduces the tree weight from $1+5+2=8$ to $1+4+2=7$. The candidate is not minimum.

Another important detail is that the condition is non-strict. Requiring every omitted edge to be strictly heavier than the path maximum would incorrectly reject valid MSTs when weights tie. The theorem guarantees minimum weight, not uniqueness; equality can allow a different spanning tree of the same weight.

Check Your Understanding

For each question, state the relevant path maximum or exchange explicitly.

In the first worked example, what tree path is used for omitted edge $24$, and what comparison must be checked?
Suppose a non-tree edge has weight $6$, and the weights on its candidate-tree path are $2,6,4$. Does this edge pass the criterion?
Explain why adding an omitted edge to a spanning tree creates a cycle, and why removing an edge from that cycle restores a spanning tree.
If an omitted edge is lighter than the maximum edge on its tree path, describe an exchange that proves the candidate is not minimum.
Why does equality in the criterion not establish that the MST is unique?