2
$\begingroup$

If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby May 16 at 16:22
  • $\begingroup$ I know that if the edge weights in G are unique, then G has a unique minimum spanning tree I'm just curious what we reverse the condition. $\endgroup$ – JKLM May 16 at 16:23
  • 2
    $\begingroup$ Trees have a unique minimum spanning tree. $\endgroup$ – David Richerby May 16 at 16:24
  • $\begingroup$ but that did not answer my question :) $\endgroup$ – JKLM May 16 at 16:25
  • $\begingroup$ If you think about it a bit more, it does. Or, rather, it contains exactly enough information for you to answer your question. $\endgroup$ – David Richerby May 16 at 16:29
5
$\begingroup$

If $G$ is a tree, it has a unique MST whatever its weights are. The weights could be unique, all the same, anything.

$\endgroup$
0
$\begingroup$

The question is: If $G$ has a unique MST, then are the edge weights necessarily distinct?

The answer is no. If $G$ is a tree with all edges having the same weight, then $G$ has a unique MST.

More generally, a minimum weight spanning tree must contain every edge that is a bridge (a bridge is an edge whose removal disconnects the graph). Consider a graph which contains two bridges, both having the same weight, and with the edges in the rest of the graph having distinct weights. Such a graph has a unique MST even though the edge weights are not all distinct because the bridges have the same weight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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