1
$\begingroup$

We all know that:

Every graph has an MST. The MST need not be unique, but it is unique if all the edge weights of the graph are distinct.

But if the weights of the edges in a connected graph are not all distinct, does it mean that there is more than one minimum spanning tree?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ not necessarily. For example if your graph is a tree, there is only one MST even if the weights are all the same $\endgroup$
    – Nephanth
    Jun 14, 2021 at 15:48

1 Answer 1

Reset to default
2
$\begingroup$

The MST can be unique even if edge weights repeat. For example, consider the graph on $\{1,\ldots,n\}$ in which the weight of $(1,2),(2,3),\ldots,(n-1,n)$ is $1$ and the weight of all other edges is $2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Toothless, why not accepting the answer by clicking the "checkmark" button underneath the vote buttons? (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    Feb 28 at 17:21

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.