Coordinatewise minimum spanning-tree weight vector
ID: coordinatewise-minimum-spanning-tree-weight-vector
Sort the edge weights of a minimum spanning tree and of any spanning tree in nondecreasing order. Then for every position. To prove it, fix a threshold and retain the graph's edges of weight at most . If this graph has connected components, 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 on its tree path, decreasing total weight. Hence exactly edges of have weight at most . 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.
New to topics? Read the docs here!