Is the inverse of MST cut property true? Why?

If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?

• Each spanning tree includes an edge that crosses the cut between $A$ and $B$. That edge, in fact, must be of weight not larger than any other edge crossing the cut between $A$ and $B$. Apr 2 '21 at 9:22
• Could you please copy the exact statement of the cut property as you have seen and paste it in the question? Thanks you. Apr 3 '21 at 1:12

This is not the case.

If an edge $$e$$ is a bridge in the graph, then every MST has to include $$e$$. There can exist some cut in which $$e$$ is the heaviest edge, but this does not change the fact that $$e$$ must be included (there is some other cut in which $$e$$ is the only - and therefore the lighest - edge).

• Nice catch on the corner case. However, this answer breaks the truth symmetry of the cut property and its inverse. Hence, I would not prefer to teach the version of cut property and its inverse implied in this answer to my students. Apr 3 '21 at 0:33

There is some ambiguity in the question. I would like to present some detailed versions, where we can enjoy both the cut property and its inverse.

Let $$G$$ be a connected, edge-weighted undirected graph, $$C$$ be a cut of $$G$$ and $$e$$ be an edge that crosses $$C$$.

The cut property of Minimum Spanning Trees (MSTs) for $$(G, C, e)$$: If, for any other edge $$e'$$ that crosses $$C$$, the weight of $$e$$ is not larger that of $$e'$$, then there is an MST of $$G$$ that contains $$e$$.

Here is the inverse proposition.

The inverse cut property of Minimum Spanning Trees (MSTs) for $$(G, C, e)$$: If there exists an edge $$e'$$ that crosses $$C$$ such that the weight of $$e$$ is larger than that of $$e'$$, then there is no MST of $$G$$ that contains $$e$$.

The inverse proposition is true. We can prove it by contradiction. Suppose there is MST $$M$$ that contains $$e$$. We can replace $$e$$ with $$e'$$ to obtain a new spanning tree. This new spanning tree has less weight than $$M$$, which is false since $$M$$ has the least weight.

Here is a different version of the cut property.

(Second version) The cut property of Minimum Spanning Trees (MSTs) for $$(G, C, e)$$: If, for any other edge $$e'$$ that crosses $$C$$, the weight of $$e$$ is smaller than that of $$e'$$, then every MST of $$G$$ contains $$e$$.

Here is the inverse proposition.

(Second version) The inverse cut property of Minimum Spanning Trees (MSTs) for $$(G, C, e)$$: If there exists an edge $$e'$$ that crosses $$C$$ such that the weight of $$e$$ is not smaller than that of $$e'$$, then there is an MST of $$G$$ that does not contain $$e$$.

The inverse proposition is true. We can prove it directly.

• If there is MST $$M$$ that does not contains $$e$$, our proof is done.
• Otherwise, let $$M$$ be an MST that does contain $$e$$. We can replace $$e$$ with $$e'$$ to obtain a new spanning tree, which does not contain $$e$$. This new spanning tree has the same weight as $$M$$. Hence, the new spanning tree is an MST, too. $$\quad\checkmark$$
• The answer is wrong. The only guarantee that some edge $e$ is not in any MST of $G$ is that for any cut $C$ such that $e$ crosses $C$, $e$ is strictly not the lightest edge to do so. There is no such guarantee when looking at just one arbitrary cut. Apr 2 '21 at 22:01
• The problem with your proofs is that you tacitly assume that one can replace any edge in a spanning tree with any other edge and end up with another spanning tree, which is not true in general. Apr 2 '21 at 22:01
• Here is another formal version of the cut property, given a connected, edge-weighted undirected graph $G$ and an edge $e$. "If there exists a cut $C$ such that $e$ is one of the lightest cuts crossing $C$, then there is an MST that contains $e$". Its inverse, "If there does not exist a cut $C$ such that $e$ is one of the lightest cuts crossing $C$, then there is no MST that contains $e$", is also true. Apr 3 '21 at 2:22
• Yes, your last version of the inverse cut property: "If there does not exist a cut $C$..." is true. However, the version that was asked about, and the versions in your answer, are not true. Apr 3 '21 at 6:45
• I think it's important to point out your error here, as if this property were true, this would imply an $O(E)$ algorithm for MST, at least in the case where all weights are different: Apr 3 '21 at 6:57