Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree?

I know the proof for if all edge weights are distinct (it does give a unique MST) and I am thinking that if two edges of minimum weight are in $G$ then I should be able to show a counter example. But so far I have not been able to produce one.

So my question is does it give a unique MST if the graph $G$ contains two minimum weight edges?

share|improve this question
add comment

2 Answers

Yes $G$ has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After adding the two minimum edges, you can't have a cycle, therefore both are in the MST.

Edit: As Paresh pointed out, this is not a complete proof, since there may be MSTs which cannot be produced by Kruskal's after permutating equally weighted edges in the sorted list. But Kruskal's is in fact able to produce any MST. Proof.

share|improve this answer
1  
This is exactly the answer I had written, before I realized that the proof is not rigorous, and probably incorrect, and so deleted my answer. Kruskal's algo gives optimal weight of MST, but says nothing about whether such an MST is the only possible one. You can't say the MST will be unique from Kruskal's. Have a look here for how the case for all distinct weights is proven. –  Paresh Dec 15 '12 at 23:03
    
Nice! Good to know that :) –  Paresh Dec 16 '12 at 13:47
    
Your observation is not an answer, and if you think your linked answer is correct, IMO is better to include it as quoted in your answer. –  user742 Dec 16 '12 at 18:24
    
@SaeedAmiri please clarify "Your observation is not an answer" –  Simon S Dec 16 '12 at 18:57
    
"Yes G has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After adding the two minimum edges, you can't have a cycle, therefore both are in the MST." –  user742 Dec 16 '12 at 19:35
show 3 more comments

Yes.

To build a minimum spanning tree you will order edges by weights from smallest to largest. An edge is included as long as it does not make a cycle. If there are two minimum weight edges, then these edges are first and second. The first two edges do not make a cycle. Therefore, since all other edges are distinct, then you will end up with one minimum spanning tree. That is, whatever order of selecing the two minimum edges, the tree would be the same. QED.

A bit of clarification: Whether you are using Prim or Kruskal, the same result applies. Here is why. Kruskal order ALL edges ascendingly. In Prim, at each node $v$, the edges are ordered ascendingly in this manner $(v,u)$ where $u$ is a neighbor of $v$. Whenever an edge $(u,v)$ is selected, the edge $(v,u)$ is deleted [note they are the same since it is an undirected edge]. The edge with smallest minimum weight $e _{min(1)} =(x,y)$ is the first in the global ordering. It also should be the first at node x and y otherwise it is not the smallest. The argument applies to the second minimum edge $e _{min(2)}$.

In general, Kruskal follows a total order of edges, while Prim uses a partial order of edges.

share|improve this answer
    
This is the third answer of the same type, the first being mine. Unfortunately, the proof I believe is not rigorous, and probably wrong, although the result might be correct, hence I deleted it. What you are referring to is the Kruskal's algorithm. It only gives the optimal weight MST, not the only MST. In other words, how do you show that there is no other MST which has the same total weight as this, but is different. For example, how do you know that Prim's algo will also generate the same MST? –  Paresh Dec 16 '12 at 9:38
    
See here for a proof of the case of all distinct weights. –  Paresh Dec 16 '12 at 9:38
    
@Paresh. I would really be interested in knowing how come it is a wrong proof. I dont mind if I am wrong. But I just want to point out that there is only "two" minimum weighted edges, and both will have to be included. –  AJed Dec 16 '12 at 14:53
    
@Paresh: Also, i dont think this is the third answer of the same type of question. When I wrote it, there were no answers. –  AJed Dec 16 '12 at 14:55
    
Probably I did not phrase it very well. I meant that the proof is incomplete. And by probably wrong, I meant the approach. I was not sure if the correct proof takes this approach or some other approach. For the reason why this proof is incomplete, take for example, the Prim's algorithm (instead of the Kruskal's). We start from a random vertex, and grow the MST from there. Then, the minimum weight edges might be encountered later, and one of them might form a cycle. In other words, what prevents one of the min weight edges being left out for a different MST with the same total weight? –  Paresh Dec 16 '12 at 15:15
show 7 more comments

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.