[Math] Graph – Minimum spanning tree

graph theorytrees

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.

Best Answer

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)$. The Graph

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$.