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.

Basically what the title says. Suppose an edge e is in every minimum spanning tree of G, does that means that e is a cut edge in G? Can I just find a counter example using the contraposition to solve this?

share|improve this question
1  
As Gerry's answer points out, this is false (for weighted graphs). What is true is that if an edge is in every spanning tree (not necessarily minimum weight) of $G$, then it is a cut edge. –  Srivatsan Nov 7 '11 at 4:44
    
@EdFox If you want to get someone's attention on this forum, you need to put @ in front of the person's username, as I've done for you here. –  Austin Mohr Nov 7 '11 at 8:01
    
Could you write a small proof of that, @Srivatsan? Also how about if G is weighted again and e is the edge of maximum weight in G? I think the two questions have to be related. –  Ed Fox Nov 7 '11 at 11:44

1 Answer 1

up vote 3 down vote accepted

If MST means minimal (weight) spanning tree (in a weighted graph), then the answer is, certainly not. Let $G$ be a complete graph wit one edge of weight 1 and lots of edges of weight 17. That weight 1 edge will be in every MST, but it's not a cut edge.

Unless I've misunderstood your definitions/conventions.

share|improve this answer

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.