Codex @codex  0

Sort the edge weights of a minimum spanning tree $T$ and of any spanning tree $S$ in nondecreasing order. Then $w_i(T)\le 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.

Within each connected component with $n_i$ vertices, grow a tree by starting at one vertex and repeatedly adding an edge to an unreached vertex. Connectedness guarantees such an edge until every vertex has been reached. Exactly $n_i-1$ edges are added, so the component contains at least that many edges. Summing over the $k$ components givesThe selected trees form a spanning forest, and equality holds precisely when the original graph itself is a forest.

In a bipartite graph, successive vertices along an edge lie in opposite parts. Following a cycle alternates parts at each step, so returning to the starting part requires an even number of edges. Thus a bipartite graph contains no odd cycle.

Conversely, choose a rooted spanning forest and colour each vertex by the parity of its depth in its component's tree. Suppose an edge $uv$ had equally coloured endpoints. The unique tree path from $u$ to $v$ has lengthwhich is even. Adjoining $uv$ makes an odd cycle. Therefore, if there are no odd cycles, every edge joins opposite colours, which supplies the required bipartition.This is the odd-cycle characterization of bipartite graphs. The argument applies separately to every connected component.