1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – John L.
    Apr 2 at 9:22
  • $\begingroup$ Could you please copy the exact statement of the cut property as you have seen and paste it in the question? Thanks you. $\endgroup$
    – John L.
    Apr 3 at 1:12
2
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Apr 3 at 0:33
-1
$\begingroup$

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$
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Highheath
    Apr 2 at 22:01
  • $\begingroup$ 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. $\endgroup$
    – Highheath
    Apr 2 at 22:01
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Apr 3 at 2:22
  • $\begingroup$ 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. $\endgroup$
    – Highheath
    Apr 3 at 6:45
  • $\begingroup$ 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: $\endgroup$
    – Highheath
    Apr 3 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.