Minimum Spanning Tree Property¶

Among all spanning trees of a weighted graph, the minimum-weight one can be found greedily because the "cut property" guarantees the minimum edge crossing any cut belongs to some MST.

Tension Addressed¶

Generality vs. Efficiency (greedy works optimally due to matroid structure)

Recognizable As¶

Growing a tree by always adding cheapest safe edge (Prim) or sorting edges globally and adding if no cycle (Kruskal); requires union-find or priority queue.

Canonical Sources¶

Boruvka, 1926; Kruskal, "On the Shortest Spanning Subtree," 1956; Prim, 1957

Transfers To¶

Network design, clustering (single-linkage), image segmentation, approximation algorithms for TSP

MST algorithms exemplify how structural properties (matroid theory) guarantee greedy optimality. The cut property provides both algorithmic guidance and correctness proof.