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?
If an edge belongs to every minimum spanning tree of $G$, is it a cut edge in $G$?
1
$\begingroup$
graph-theory
-
1As 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. – 2011-11-07
-
0@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. – 2011-11-07
-
0Could 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. – 2011-11-07
1 Answers
3
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.