Graph MST

Question

For a simple, undirected, weighted graph each edge havind distinct weight, How is it possible that there can be more than $1$ second best minimum spanning tree?

Answer 1

Make a complete graph of 4 vertices. Assign weight=1 to three edges and weight=2 to 4th edge and both diagonals.

 

Now weight of minimum spanning tree= 3. It's unique here.

Weight of second best spanning tree=4. But its not unique in this graph. 4 such spanning trees are possible.

 

Now another example where weights are distinct. A graph like above but with one diagonal. Let 4 edges have weights 1,2,3,5 and weight of diagonal is 4.

MST will consist of (1,2,3).

Two second best MSTs will be (1,2,5) and (1,3,4). So again, second best MST is not unique.

Comments

each edge having distinct edge.

---

@thor

Thanks!

Updated

---

Its incorrect  The second best MST would be (1,2,4) which is unique in your example.