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?
7
$\begingroup$
$\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$
$\endgroup$
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$
