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.

  • $\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, 2019 at 16:54


Browse other questions tagged or ask your own question.