0
$\begingroup$

How to prove that the heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree? by heaviest edge of any Spanning tree i mean considering any possible Spanning tree, we have to prove that the heaviest edge in mst is not heavier than heaviest edge of that spanning tree.

$\endgroup$
2
  • 1
    $\begingroup$ When your question is closed, please don't re-post it. Instead, revise it based on the feedback you have received. Once you have edited it, it can be considered for re-opening. Also, I don't see that you have responded to the prior feedback, asking what you have tried. $\endgroup$
    – D.W.
    Nov 23, 2023 at 8:45
  • $\begingroup$ We are not particularly looking for that contain the text of an exercise-style task along with a "I don't even know how to start". Our goal is to build up an archive of knowledge that will be useful to others. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Nov 23, 2023 at 8:46

1 Answer 1

1
$\begingroup$

Let $e^*$ be the heaviest edge in an MST $T$, and let $A$ and $B$ be the vertices of the two connected components of $T - e^*$.

Now, by the cut property, $e^*$ is a cheapest edge with one endpoint in $A$ and one endpoint in $B$.

Since any spanning tree $T'$ must have an edge $e$ with one endpoint in $A$ and one in $B$, this means that $T'$ has an edge of cost at least the cost of $e^*$.

$\endgroup$

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.