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.


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

  • 1
    $\begingroup$ Interesting. Before you edited the question, I read it as meaning the graph was purely a circle/cycle and nothing else, in which case the claim is true. After the edit, the claim is now false... $\endgroup$ – Rawling Mar 11 '11 at 14:11
  • $\begingroup$ If you click the "x minutes ago" link you can see a history. $\endgroup$ – Rawling Mar 11 '11 at 14:23
  • $\begingroup$ I just looked at the original post, and I would still edit it the way I did. But you are right, it might have been my misunderstanding of the question. $\endgroup$ – utdiscant Mar 11 '11 at 14:24
  • $\begingroup$ Thank u, but why (a-b,b-c,c-d,d-e) is not MST? $\endgroup$ – user8069 Mar 11 '11 at 15:20
  • $\begingroup$ The weight of (a-b,b-c,c-d,d-e) is 1+1+1+100=103, which is more than the one of weight 4. $\endgroup$ – utdiscant Mar 11 '11 at 15:26

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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy