# How do I write this proof more formally?

So the question asks, given that we have a undirected graph with unique edge weights, prove that the graph has a unique minimum spanning tree. My Proof: If the graph has unique edge weights, we can list the edges as $$E_1,E_2,\ldots, E_N, \text{ s.t. } E_1 < E_2 < E_3 < \cdots < E_N.$$

Then applying Kruskal's Algorithm, we can say that the edges that will be in our minimum spanning tree will be all edges in the above list such that as we go through the list, the next element added does not create a cycle. Since the only time we are faced with multiple decision points is when there are two edges of the same weight to choose from, and since the edge weights are distinct, we are never confronted with a decision to choose between two edges, and hence our minimum spanning tree is unique.

But I feel as though the part about decision points is flimsy. Any advice?

## 2 Answers

Suppose the graph has two MSTs. We list the first MST's edges increasingly according to the weights. Then we list the second MST's edges by the same way. Then we check the two lists. Two lists are denoted by $L_1$ and $L_2$. $L_{ij}$ represents the $j$-th edge in $L_i$. Clearly, there exists $k$ such that the weight of $L_{1k}$ is less than that of $L_{2k}$ and $L_{1j}$ is the same as $L_{2j}$ for $j<k$. Then we add $L_{1k}$ to the second MST, and some cycle appears. According to the Kruskal's algorithm, we could delete $L_{2j}$ for some $j>k$ to make $L_2$ the MST again. Clearly the weight of the new $L_2$ is lighter than that of the original $L_2$. Contradiction!

In proving the optimality of Kruskal's algorithm, you show that the spanning tree that the algorithm generates is at least as good as any other spanning tree. The same argument shows that the tree is better than any other spanning tree if the weights are unique.

• Are you referring to the argument presented here ? I don't see how the argument presented in Wikipedia could be extended to show that unique weights implies a unique minimum spanning tree. Could you explain further? – I Love Cake Mar 7 '11 at 9:42
• In the argument, you consider an edge $e$ chosen by the algorithm, and an alternative edge $f$ which is in another MST. We exchange them to show that Kruskal's choice is also good. In your case, $e$ is strictly better than $f$, so the alternative couldn't have been a MST. – Yuval Filmus Mar 7 '11 at 16:10