3
$\begingroup$

This question already has an answer here:

Given the following statement:

For a graph $G$, consider its minimum spanning tree $T$ and let $e = (a,b)$ be an edge that is not a light edge for a given cut $C$. Then $e$ never belongs to $T$.

Intuitively, I believe that the above statement must be true since in order to make an MST we always take (one of) the lightest edges available that cross the cut, but am I not sure how to approach a proof, or if my intuition is right.

$\endgroup$

marked as duplicate by Apass.Jack, D.W. Mar 28 at 18:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Try a proof by contradiction. 1) Assume $T$ is an MST in $G$. 2) Assume $e$ is not a light edge for a cut $C$, but that $e$ belongs to $T$. 3) Use (2) to prove that (1) does not hold. 4) Conclude a contradiction, thus (2) is not possible to be true. $\endgroup$ – ryan Mar 28 at 16:54