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.

If any edge from a given spanning tree T0 is contained in some minimum spanning tree T*, does this imply that T0 is also a minimum spanning tree ?

Right now, I'm trying to draw on paper some graphs to prove that it doesn't. Please correct me if it does, or help me find an example if it doesn't.

Thanks in advance.

P.S. smb please add MST or spanning-trees tag.

share|improve this question
    
Any two spanning trees have the same number of edges, so if all edges in one spanning tree are also edges in the other one, then the two are in fact the same! –  Mariano Suárez-Alvarez Nov 28 '10 at 1:25
    
a edge from T0 may be in T*1 and all the other edges, let;s say, in T*2.. both T*1 and T*2 are MST.. does this imply that T0 is also MST ? –  sdadffdfd Nov 28 '10 at 1:28
add comment

1 Answer 1

up vote 4 down vote accepted

Consider a triangle with edge weights $2,2,1$.

share|improve this answer
    
wow, really simple.. now the graphs I was drawing seem like aliens compared to this one, thanks. –  sdadffdfd Nov 28 '10 at 1:36
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.