Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
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... –  Rawling Mar 11 '11 at 14:11
    
If you click the "x minutes ago" link you can see a history. –  Rawling Mar 11 '11 at 14:23
    
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. –  utdiscant Mar 11 '11 at 14:24
    
Thank u, but why (a-b,b-c,c-d,d-e) is not MST? –  user8069 Mar 11 '11 at 15:20
    
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. –  utdiscant Mar 11 '11 at 15:26
show 1 more comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.