= Coordinatewise minimum spanning-tree weight vector
Sort the <edge weights> of a <minimum spanning tree> $T$ and of any <spanning tree> $S$ in nondecreasing order. Then $w_i(T)\leq w_i(S)$ for every position. To prove it, fix a threshold $t$ and retain the graph's edges of weight at most $t$. If this graph has $c$ <connected components>, $T$ contains a <spanning forest> of each component using those edges: otherwise a light edge joining two of its pieces could replace an edge heavier than $t$ on its tree path, decreasing total weight. Hence exactly $|V|-c$ edges of $T$ have weight at most $t$. No other <spanning tree> can have more, since its retained edges form a <forest> inside those components. These threshold counts imply the coordinatewise inequality for sorted weights.
Back to article page
