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
  • $\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 at 15:48
1
$\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$

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.