5
$\begingroup$

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?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paresh
    Dec 15, 2012 at 23:03
  • $\begingroup$ Nice! Good to know that :) $\endgroup$
    – Paresh
    Dec 16, 2012 at 13:47
  • $\begingroup$ 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. $\endgroup$
    – user742
    Dec 16, 2012 at 18:24
  • $\begingroup$ @SaeedAmiri please clarify "Your observation is not an answer" $\endgroup$
    – Simon S
    Dec 16, 2012 at 18:57
  • $\begingroup$ "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." $\endgroup$
    – user742
    Dec 16, 2012 at 19:35
3
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – Paresh
    Dec 16, 2012 at 9:38
  • $\begingroup$ See here for a proof of the case of all distinct weights. $\endgroup$
    – Paresh
    Dec 16, 2012 at 9:38
  • $\begingroup$ @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. $\endgroup$
    – AJed
    Dec 16, 2012 at 14:53
  • $\begingroup$ @Paresh: Also, i dont think this is the third answer of the same type of question. When I wrote it, there were no answers. $\endgroup$
    – AJed
    Dec 16, 2012 at 14:55
  • $\begingroup$ 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? $\endgroup$
    – Paresh
    Dec 16, 2012 at 15:15
0
$\begingroup$

Yes.

Here is a proof that does not rely on any algorithm such as Kruskal's algorithm or Prim's algorithm.

For any cycle $C$ in $G$, $C$ has 3 or more than edges, one of which must weigh differently from the (global) minimum weight. So the maximum edge-weight of $C$ is not the global minimum weight. Since except two edges of the global minimum weight, all other edges in $G$ weigh distinctly, $C$ must have a unique heaviest edge. Let $e$ be an arbitrary edge in $G$. If $e$ is not the unique heaviest edge in any cycle, then it is not a heaviest edge in any cycle. According to the characterization by "extreme cycle edge" of uniqueness of MST, $G$ has a unique MST.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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