Description

Suppose you are given a connected graph G with edge costs that are all distinct. Prove that G has a unique minimum spanning tree.

Suppose we have a graph G, where all but two of the edges have distinct weights – that is, two edges have the same weight, and all of the others are distinct. Which of these is true: a) G has a unique MST, b) G has more than one MSTs or c) Sometimes G has a single MST, sometimes G has more than 1 MST. Prove your answer is correct.