# Show that there's a unique minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$.

I thought that the proof can be done for example by contradiction, saying that we have $2$ different MST meaning that somewhere was possible to pick from more edges, so $w(e) = w(f)$ for $e\neq f$, contradiction. Apparently this is not correct.

How would you show that a graph has a unique MST if all edges have distinct weights?

If $T_1$ and $T_2$ are distinct minimum spanning trees, then consider the edge of minimum weight among all the edges that are contained in exactly one of $T_1$ or $T_2$. Without loss of generality, this edge appears only in $T_1$, and we can call it $e_1$.

Then $T_2 \cup \{ e_1 \}$ must contain a cycle, and one of the edges of this cycle, call it $e_2$, is not in $T_1$.

Since $e_2$ is a edge different from $e_1$ and is contained in exactly one of $T_1$ or $T_2$, it must be that $w ( e_1 ) < w ( e_2 )$. Note that $T = T_2 \cup \{ e_1 \} \setminus \{ e_2 \}$ is a spanning tree. The total weight of $T$ is smaller than the total weight of $T_2$, but this is a contradiction, since we have supposed that $T_2$ is a minimum spanning tree.

• How do we know that $w ( e_1 ) < w ( e_2 )$? – Alexander Mar 4 '17 at 23:57
• @Alexander Because $e_1$ is the edge of least weight that is contained in exactly one of the MSTs, and $e_2$ is a different edge that is contained in exactly one of the MSTs. – user642796 Mar 5 '17 at 3:49
• Is $e_1$ the edge of least weight out of the edges of $T_1 \cup T_2$, which is in either $T_1$ or $T_2$? Or is $e_1$ the edge of least weight out of the edges of $T_1 \bigtriangleup T_2$? – Alexander Mar 6 '17 at 1:43
• I suspect it's the latter of two, otherwise I don't understand how we know this edge isn't in both $T_1$ and $T_2$. – Alexander Mar 6 '17 at 1:47
• @Alexander As I said, $e_1$ is the edge of least weight that is contained in exactly one of the MSTs. If it was in both $T_1$ and $T_2$ it would not be contained in exactly one of the MSTs. – user642796 Mar 6 '17 at 3:41

A proof using cycle property:

Let $G=(V,E)$ be the original graph.

Suppose there are two distinct MSTs $T_1=(V,E_1)$ and $T_2=(V,E_2)$. Since $T_1$ and $T_2$ are distinct, the sets $E_1-E_2$ and $E_2-E_1$ are not empty, so $\exists e\in E_1-E_2$.

Since $e\notin E_2$, adding it to $T_2$ creates a cycle. By cycle property the most expensive edge of this cycle (call it $e'$) does not belong to any MST. But

If $e'=e$ then $e'\in E_1$ (because $e\in E_1-E_2$)
If $e'\neq e$ then $e'\in E_2$

Both cases are contradicting with the fact that $e'$ is not in any MST.

The best explanation I found was on wikipedia, Proof:

1. Assume the contrary, that there are two different MSTs $A$ and $B$.
2. Since $A$ and $B$ differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let e1 be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume $e1$ is in $A$.
3. As $B$ is a MST, $\{e1\}\cup B$ must contain a cycle $C$.
4. As a tree, $A$ contains no cycles, therefore $C$ must have an edge $e2$ that is not in $A$.
5. Since $e1$ was chosen as the unique lowest-weight edge among those belonging to exactly one of $A$ and $B$, the weight of $e2$ must be greater than the weight of $e1$.
6. Replacing $e2$ with $e1$ in $B$ therefore yields a spanning tree with a smaller weight.
7. This contradicts the assumption that $B$ is a MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees [1].