top of page

We are given a weighted graph G in which edge weights are not necessarily distinct. Can graph G have more than one minimum spanning tree (MST)? If yes, give an example, else justify.

The theorem is that if edge weights are distinct then a graph will have only one minimum spanning tree. However, if the edge weights are not necessarily distinct, then the graph may have more than one spanning tree.


For example, let us consider the following graph:


This graph has three minimum-spanning trees. Let us consider two of them


With this example, we have proved that minimum spanning tree need not be unique.

38 views0 comments

コメント


bottom of page