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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.