Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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!

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.