What Uniqueness Means
A minimum spanning tree is a spanning tree of minimum total weight. Even when the graph is connected, there may be more than one spanning tree with that minimum weight. To decide whether the minimum is unique, it is useful to compare the weights of edges that a candidate tree leaves out with the paths joining their endpoints inside the tree.
Throughout, \(G=(V,E)\) is a finite, connected, simple graph with a real weight \(w(e)\) assigned to each edge \(e\). A spanning tree is a connected, acyclic subgraph containing every vertex. Its weight is the sum of the weights of its edges. A minimum spanning tree, abbreviated MST, is a spanning tree of least weight. A path in a tree between any two vertices is unique. If \(T\) is a spanning tree and \(e=uv\notin E(T)\), write \(P_T(e)\) for the unique \(u\)-\(v\) path in \(T\).
This criterion applies to a specified MST. It also handles a graph that is already a tree: there are no omitted edges, the condition is vacuously true, and the graph has only one spanning tree.
Proof. First, since \(T\) is an MST, an omitted edge \(e=uv\) cannot be lighter than any edge \(f\) on \(P_T(e)\). If \(w(e)<w(f)\), adding \(e\) to \(T\) creates a cycle consisting of \(e\) and \(P_T(e)\); removing \(f\) from that cycle gives a spanning tree of weight \(w(T)+w(e)-w(f)<w(T)\), contradicting minimality.
If \(w(e)=w(f)\) for some \(f\in P_T(e)\), then adding \(e\) and removing \(f\) gives a different spanning tree with the same weight as \(T\). It is therefore another MST, so \(T\) is not unique. This proves that uniqueness requires every omitted edge to be strictly heavier than every edge on its tree path.
Conversely, suppose the strict inequalities hold, and suppose there is another MST \(T'\ne T\). Choose an edge \(e=uv\in E(T')\setminus E(T)\). Removing \(e\) from \(T'\) separates its vertices into two sets, with \(u\) and \(v\) in different sets. The path \(P_T(e)\) must cross between those sets, so it contains an edge \(f\) crossing the same separation. The only edge of \(T'\) crossing that separation is \(e\); hence \(f\notin E(T')\). By the assumed condition, \(w(f)<w(e)\). Adding \(f\) to \(T'-e\) reconnects the two sets and gives a spanning tree of weight \(w(T')-w(e)+w(f)<w(T')\), contradicting that \(T'\) is an MST. Thus \(T\) is unique. \(\square\)
A Cycle Condition: Sufficient, Not Necessary
A cycle has a unique heaviest edge if one of its edges has weight strictly greater than every other edge on that cycle. The familiar cycle exchange explains why this condition is useful.
Proof. Let \(e=uv\) be the unique heaviest edge on a cycle, and suppose an MST \(S\) contains \(e\). Removing \(e\) from \(S\) separates \(u\) from \(v\). The rest of the cycle is a \(u\)-\(v\) path, so at least one edge \(f\) on that path crosses between the two resulting parts. Since \(e\) is uniquely heaviest, \(w(f)<w(e)\). Replacing \(e\) by \(f\) reconnects the parts and produces a spanning tree of smaller weight, contradicting the minimality of \(S\). Therefore no MST contains \(e\). \(\square\)
Proof. Suppose instead that \(T\) and \(T'\) are distinct MSTs. Choose \(e=uv\in E(T')\setminus E(T)\), and consider the cycle formed by adding \(e\) to \(T\); it consists of \(e\) and \(P_T(e)\). By assumption this cycle has a unique heaviest edge. If that edge is \(e\), the lemma says \(e\) belongs to no MST, contradicting \(e\in E(T')\). If the unique heaviest edge is an edge of \(P_T(e)\), it belongs to \(T\), again contradicting the lemma. These cases cover every edge of the cycle, so two distinct MSTs cannot exist. \(\square\)
The implication is one-way. The condition about every cycle is sufficient, but it is not necessary: a cycle can have tied heaviest edges even when those edges are irrelevant to the minimum spanning tree. The following example makes this distinction explicit.
Worked Example: Tied Cycle Weights but a Unique MST
Let \(G\) have vertex set \(V=\{0,1,2,3\}\). Its edges and weights are \(01,02,03\), each of weight \(1\), and \(12,23,13\), each of weight \(10\). The three edges among \(1,2,3\) form a cycle whose three edges are all tied for heaviest. Thus the condition that every cycle have a unique heaviest edge fails.
Consider the spanning tree \(T\) with edges \(01,02,03\). Its total weight is \(1+1+1=3\). The omitted edge \(12\) has tree path \(1,0,2\), whose two edges each have weight \(1\); hence \(10>1\) for both path edges. The omitted edge \(23\) has path \(2,0,3\), again with weights \(1,1\), and \(10>1\) for both. The omitted edge \(13\) has path \(1,0,3\), also with weights \(1,1\), and \(10>1\) for both. The uniqueness theorem therefore shows that \(T\) is the unique MST.
Check: independently, any spanning tree that omits a spoke, such as \(01\), must connect vertex \(1\) using at least one of the weight-\(10\) edges \(12\) or \(13\). Its other two edges have weights at least \(1\) each, so its total weight is at least \(10+1+1=12>3\). The same reasoning applies if the omitted spoke is \(02\) or \(03\). Thus no other spanning tree can tie the weight \(3\) of \(T\), despite the tied heaviest edges on the cycle \(1,2,3,1\).
Worked Comparisons
Worked Example: Distinct Weights Give a Unique MST
Let \(V=\{1,2,3,4\}\), with edges \(12,23,34,14,13\) having weights \(1,2,3,4,5\), respectively. The tree \(T\) with edges \(12,23,34\) has total weight \(1+2+3=6\).
Check the two omitted edges. For \(14\), the tree path is \(1,2,3,4\), with edge weights \(1,2,3\); its weight \(4\) is greater than all three. For \(13\), the tree path is \(1,2,3\), with edge weights \(1,2\); its weight \(5\) is greater than both. The uniqueness criterion proves that \(T\) is the unique MST.
Check: the total for \(T\) is \(1+2+3=6\). The strict path comparisons are \(4>1,2,3\) and \(5>1,2\), so the criterion applies to each omitted edge. In general, if all edge weights are distinct, every cycle has a unique heaviest edge: among finitely many distinct weights on a cycle, exactly one is largest. The cycle theorem then guarantees a unique MST.
Worked Example: A Tied Heaviest Edge Can Produce Two MSTs
Let \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\), with weights \(w(12)=1\), \(w(23)=2\), and \(w(13)=2\). A spanning tree on these three vertices uses two edges. The tree with \(12,23\) has weight \(1+2=3\), and the tree with \(12,13\) also has weight \(1+2=3\). The remaining spanning tree, with \(23,13\), has weight \(2+2=4\).
Therefore the minimum weight is \(3\), attained by two distinct spanning trees. The only cycle is the triangle, and its two edges of weight \(2\) are tied for heaviest. This example shows that a tied maximum on a cycle can accompany nonuniqueness, but the preceding example shows that a tied maximum does not force nonuniqueness.
Check: the three possible two-edge choices have totals \(1+2=3\), \(1+2=3\), and \(2+2=4\). Exactly the first two attain the minimum.
Common Pitfall and Practical Test
A common mistake is to claim that an MST is unique if and only if every cycle has a unique heaviest edge. The forward implication is false. In the four-vertex example, the unique MST has weight \(3\), while the cycle \(1,2,3,1\) has three edges of weight \(10\). The correction is to use the cycle condition only as a sufficient test, and to use the tree-path criterion for an exact test once an MST \(T\) is known.
For that exact test, inspect each edge \(e\notin E(T)\) and compare its weight with every edge on \(P_T(e)\). If any omitted edge ties a path edge, exchanging those two edges produces another spanning tree of the same weight, so the MST is not unique. If every omitted edge is strictly heavier than every edge on its path, the theorem proves uniqueness. Distinct weights guarantee the cycle condition, and hence uniqueness, but they are not required: the four-vertex example has several edges of equal weight and still has a unique MST.
If \(G\) has a single vertex and no edges, its empty spanning tree is its only spanning tree. There are no cycles and no omitted edges to test, so both the cycle condition and the path criterion hold vacuously. This is consistent with the same conclusions.
Check Your Understanding
For each question, use the definitions and exchange arguments developed above.
- For a proposed MST \(T\), what comparison must hold between an omitted edge and every edge on its path in \(T\) for \(T\) to be unique?
- Explain why an omitted edge that ties an edge on its tree path rules out uniqueness.
- Why can a cycle with a unique heaviest edge not have that edge in any MST?
- Is a unique heaviest edge on every cycle necessary for a unique MST? Give the relevant example from this tutorial.
- Why do distinct edge weights guarantee a unique MST, and why are distinct weights not necessary?