Graph - Minimum spanning tree I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$).
Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum spanning tree.
I am trying to think about contradiction, but I can't find one. All my examples create more than one Minimum Spanning Tree.
Thanks a lot.
 A: The claim is false.
Consider a graph $G$ with points $a,b,c,d,e$ and edges $(a,b),(b,c),(c,d),(d,e),(e,a),(a,d)$ where all edges have weight 1, except $(a,b)$ and $(a,e)$ which have weight 100. Then there is only one minimum spanning tree, namely $(b,c),(c,d),(d,e),(a,e)$.

If instead the claim was the following: "If a graph $G$ is a cycle, and two of the edges $e_1$ and $e_2$ have weight $w$ which is the maximum weight in $G$, then there are at least two different minimum spanning trees in $G$"
Then the claim is true. Consider some spanning tree $T$ in $G$. Since $T$ is spanning, one of the edges, lets say $e_1$ with weight $w$ must be in $T$. Now consider a new tree $T' = T - e_1 + e_2$. Now one can easily show that $T'$ is also spanning and has the same weight as $T$.
A: Of course, usually there is a group of MST(minimum spanning tree) and what really represents the MST is it's weight and not the exact tree, and your example it's exactly where more the one MST come from.
claim: if the graph has a cycle with two equal weighted edges then it has at least TWO MST, prof: you have MST containing edge a1 if you close the cycle with a2 and remove a1 you have another MST!
