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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityCurrently 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?
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$