# 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?

-

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 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