Is there any minimum spanning tree that contains the maximum-weight edge on some cycle?

Question

The origin problem is from the exercise of Introduction of Algorithm.

23.1-5 Let e be a maximum-weight edge on some cycle of connected graph G=(V, E). Prove that there is a minimum spanning tree of G'=(V, E - {e}) that is also a minimum spanning tree of G. That is, there is a minimum spanning tree of G that does not include e.

The question is that: I think the proposition that all the minimum spanning tree of G do not include e is right. The e is the only one maximum-weight edge on some cycle. Is it ?

Update: 2016-10-28 20:21

Add the restriction that e is the only one maximum-weight edge on some cycle.

Answer 1

One test case is when there are nodes labeled 0..n-1 and there are links only between node i and node (i + 1) mod n (that is, a ring). In this case the minimum spanning tree is created by leaving out just one of the links. If e is the unique maximum weight edge it is not in the unique spanning tree, which is all the other links. If there is more than one edge of maximum weight then there are as many different minimum spanning trees as there are edges of maximum weight, each one of them leaving out a different edge of maximum weight and keeping the other ones in.

Consider the case when there is just one edge of maximum weight. Supposing somebody hands you a minimum spanning tree that uses this edge. Delete it from the tree, giving you two disconnected components. Now try adding each of the other edges in the cycle, one at a time. If the edge doesn't connect the two components, delete it again. If any of the edges connect the two components, you have a spanning tree of smaller weight than before, so it can't have been a minimum spanning tree. Can it be the case that none of the edges connect the two components? Adding an edge that doesn't connect the two components doesn't increase the set of nodes reachable from either component, so if no single edge connected the two components, adding all of them at the same time won't. But we know that adding all of these edges adds a path that connects the two nodes connected by the previous maximum weight edge, so one of the edges must connect the components. So our original so-called minimum spanning tree wasn't, and an edge which is of unique maximum weight in a cycle can't be part of a minimum spanning tree.

Answer 2

Your guess is correct： all the minimum spanning tree of G do not include e is right.

First we need to prove: e is not a light edge crossing any cut of G.

Let C be any cut that cuts e, since e is in a cycle, so e is not a light edge for any of those cuts, and all the other cuts won't have the edge e crossing it, we won't have that the edge is light for any of those cuts either.

Then we need to prove: if e is not a light edge crossing any cut of G, then all the minimum spanning tree of G do not include e. Which is exactly the inverse proposition of 23.1-3.