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?
Graph Theory – Must Minimum Weight Spanning Tree Contain Least Weight Edge of Every Vertex?
graph theorytrees
Related Solutions
The claim is false.
Consider a graph $G$ with points $a,b,c,d,e$ and edges $(a,b),(b,c),(c,d),(d,e),(e,a),(a,d)$ where all edges have weight 1, except $(a,b)$ and $(a,e)$ which have weight 100. Then there is only one minimum spanning tree, namely $(b,c),(c,d),(d,e),(a,e)$.
If instead the claim was the following: "If a graph $G$ is a cycle, and two of the edges $e_1$ and $e_2$ have weight $w$ which is the maximum weight in $G$, then there are at least two different minimum spanning trees in $G$"
Then the claim is true. Consider some spanning tree $T$ in $G$. Since $T$ is spanning, one of the edges, lets say $e_1$ with weight $w$ must be in $T$. Now consider a new tree $T' = T - e_1 + e_2$. Now one can easily show that $T'$ is also spanning and has the same weight as $T$.
Let $T$ be a local minimum spanning tree that is not a global minimum. Let $e_1,\ldots,e_m$ the edges of $T$ ordered by non-decreasing weight. Let $T'$ be a minimum weight spanning tree that coincides with $T$ on the largest possible begin segment, so we may assume $T'$ has edges $e_1,\ldots,e_{n-1},f_n,\ldots,f_m$ (again ordered by non-decreasing weight) and $f_n\ne e_n$. Let $w$ be the weight function in our graph.
We claim that $w(f_n)<w(e_n)$: indeed, if $w(e_n)\leq w(f_n)$ then $e_1,\ldots,e_{n-1},e_n$ would be a valid startup for Kruskal's algorithm and would lead to a minimum weight spanning tree that coincides with $T$ on a larger initial segment.
$T+f_n$ contains exactly one cycle $C$. The edges of $C$ different from $f_n$ cannot all be in $\{e_1,\ldots,e_{n-1}\}$ or we would have a cycle in $T'$. So we find at least one edge $f$ on $C$ that is different from $e_1,\ldots,e_{n-1}$ and $f_n$. But then $w(f)\geq w(e_n)>w(f_n)$, so $T+f_n-f$ is a spanning tree with a smaller total weight that is a neighbour of $T$ in the spanning tree graph. Contradiction.
(I left some small details for you to prove. Let me know if they cause trouble).
Note that this proves the slightly stronger statement, that each non-minimal tree has a neighbour of strictly smaller total weight.
Related Question
- [Math] the “true” minimum spanning forest of a connected graph
- [Math] Graph $G$ with different weights on edges has unique minimum spanning tree
- [Math] Let $e$ be an edge of minimum weight in the connected weighted graph $G$. Every minimum spanning tree of $G$ contains $e$
- [Math] Do the algorithms of Prim and Krusksal always produce the same minimum spanning tree, given the same tiebreak criterion
Best Answer
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$