7
$\begingroup$

Currently learning about spanning trees and using Kruskal's algorithm and I was wondering whether a minimum weight spanning tree of a weighted graph must contain one of the least weight edges of every vertex.

Is it the case?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Yes you're right, the title could have been clearer. My bad, it's my first question here. Also, is it necessary to have a body? I didn't really need one, that's why it's a bit redundant. $\endgroup$ – K O'Reilly Mar 3 '16 at 21:16
  • $\begingroup$ Congratulations on getting your first Question answered so promptly! Yes, it is important to include the actual problem in the body text of the Question. Otherwise Readers may be at a loss to connect the necessarily terse statement in the title with what context you provide about where you found the problem or where you got stuck solving it. Problems posted without such context are frequently downvoted. To post mathematical expressions, this site supports MathJax and $\LaTeX$. $\endgroup$ – hardmath Mar 3 '16 at 22:11
3
$\begingroup$

Yes.

Let's assume that's not true, i.e. there exists a vertex $v$ such that MST does not use any of its smallest weight edges (there may be more than one). Let $e$ be any of such edges, then you can add $e$ to MST and then remove the other edge of $v$ on that cycle, which by definition was of strictly greater weight. We reach a contradiction with the weight of MST.

I hope this helps $\ddot\smile$

|cite|improve this answer
$\endgroup$

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.