[Solved]: When is the minimum spanning tree for a graph not unique

Problem Detail: 

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G?

I know that the MST is unique when all of the weights are distinct, but you can't reverse this statement. If there are muliple edges with the same weight in the graph, there may be multiple MSTs but there might also be just one:

In this example, the graph on the left has a unique MST but the right one does not.

The closest I could get to finding conditions for non-uniqueness of the MST was this:

Consider all of the chordless cycles (cycles that don't contain other cycles) in the graph G. If in any of these cycles the maximum weighted edge exists multiple times, then the graph does not have a unique minimum spanning tree.

My idea was that for a cycle like this

with n vertices, you can leave out exactly one of the edges and still have all of the vertices be connected. Therefore, you have multiple choices to remove the edge with the highest weight to get a MST, so the MST is not unique.

However, I then came up with this example:

You can see that this graph does have a cycle that fits my condition: (E,F,G,H) but as far as I can see, the minimum spanning tree is unique:

So it seems like my condition isn't correct (or maybe just not completely correct). I'd greaty appreciate any help on finding the necessary and sufficient conditions for the non uniqueness of the minimum spanning tree.

Asked By : Keiwan

Answered By : HueHang

in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2.

Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$.

If there exists an edge $e=\{v,w\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest edge-weight from $F\cap C$, then we can create a second MST by swapping an edge from $F\cap C$ with edge-weight $m$ with $e$. Thus we do not have uniqueness.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60464