Show that a graph has a unique MST if all edges have distinct weights

Question

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree or MST). (Use contradiction and make sure to keep track of the costs of the different trees involved.)

Here is my attempt:

Proof by contradiction

Assume that there is more than one cheapest tree, A and B. Assume that tree A and B are different and have the same weight. Let says that the smallest difference in edge cost between A and B is 1. Now, change one of the random edge (not contain in B) in A by half. This does not affect the path or order. However, A is cheaper than B now. This is contradiction. Thus, the original statement still hold.

Is this the correct logic? How do I write it out formally?

Answer 1

The question is about showing that the minimal spanning tree is unique if all the edges have different weights. If one goes through any of the greedy algorithms (Prim, Kruskal..) for finding a minimal spanning tree one notices that the weights do not need to be added, just compared, that is, the weights should be elements of a totally ordered set. Moreover, the minimal spanning tree $T$ obtained by the algorithm has the property that for any other spanning tree $T'$, if we consider the weight in increasing order for $T$, respectively $T'$ $$(w_1, \ldots w_{n-1})$$ and $$(w'_1, \ldots w'_{n-1})$$ we have $$w_i \le w'_i$$ for all $i$. This is due to the fact that we can get from $T$ to $T'$ by a sequence of intermediate trees so that at each step the next tree is obtained from the previous one by substituting an edge with another edge of $\ge $ weight.

If all the edges have distinct weights then $T$ thus obtained is strictly better than any other tree since at each step we substitute an edge with another one of a strictly large weight (the weights cannot be the same). Hence the uniqueness.

Answer 2

Suppose there are two minimum trees, $A$ and $B$. Let $e$ be the edge in just one of $A,B$ with the smallest cost. Suppose it is in $A$ but not $B$. Suppose $e$ is the edge $PQ$. Then $B$ must contain a path from $P$ to $Q$ which is not simply the edge $e$. So if we add $e$ to $B$, then we get a cycle. If all the other edges in the cycle were in $A$, then $A$ would contain a cycle, which it cannot. So the cycle must contain an edge $f$ not in $A$. Hence, by the definition of $e$ (and the fact that all edge-costs are different) the cost of $f$ must be greater than the cost of $e$. So if we replace $f$ by $e$ we get a spanning tree with smaller total cost. Contradiction.