For a connected, weighed, undirected graph G: G has a unique MST, if for every cut of G there is a unique minimum weight edge crossing the cut.

Is this statement true?

I think false because for the following graph in the given link there can be multiple MSTs.

enter image description here

  • $\begingroup$ I think the minimum weight edge in the question is not necessary a minimum weight edge in the whole $G$ but only a minimum weight edge among the edges crossed by the cut. Then for the graph from the picture a cut consisting of the upper left vertex has two minimum weight edges. $\endgroup$ Commented Mar 2, 2019 at 3:28
  • $\begingroup$ Maybe we can prove the statement using a fact that the condition imposed on the graph assures that Jarník-Prim's algorithm build a unique minimum spanning tree from any given starting vertex. $\endgroup$ Commented Mar 2, 2019 at 3:28


You must log in to answer this question.

Browse other questions tagged .