0
$\begingroup$

Does an edge never being the largest weight in any cycle imply that it is included in the MST? I believe the answer is not, but can't think of a counterexample. I know that one guarantees an edge is in the MST with the cut property, but was wondering if this is equivalent.

$\endgroup$

1 Answer 1

0
$\begingroup$

Consider $G = (V, E, w)$ an undirected weighted connect graph, and $T = (V, F)$ a minimum spanning tree of $G$.

Assume there exists $a\in E$ such that $w(a)$ is never the largest in any cycle containing $a$, and $a\notin F$.

Then $(V, F\cup \{a\})$ contains a cycle. Do you see how to construct a spanning tree of $G$ with weight less than $w(T)$?

$\endgroup$
1
  • $\begingroup$ Yes, we have to apply the cycle property to the cycle that was created. The resulting tree would have total weight less than the minimum spanning tree. Thus, such tree cannot be the MST, and $a$ must be in the MST. $\endgroup$
    – joeren1020
    Dec 4, 2023 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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