the matroid-greedy theorem

Instead of inventing a fresh correctness proof for each greedy algorithm, what if one theorem certified a whole family at once? The matroid-greedy theorem does exactly that. It says: take any matroid, attach a weight to each element, and the simple greedy rule of grabbing heavy elements while staying independent will always produce a maximum-weight basis. No per-problem cleverness required.

Precisely: let M be a matroid on ground set E with a nonnegative weight on each element. Run greedy — sort E from heaviest to lightest, start with the empty set, and consider each element in turn, adding it if and only if the result is still independent. The theorem guarantees the resulting independent set has maximum total weight among all independent sets (and is a basis). Remarkably the converse also holds: if this greedy rule yields an optimal independent set for EVERY choice of weights, then the independence system must be a matroid. So matroids are exactly the structures on which weighted greedy is universally correct — this is sometimes called the Rado-Edmonds theorem. The proof that greedy works hinges on the exchange property: whenever greedy's partial set is smaller than some hypothetically better set, the exchange property lets greedy borrow an element it has not yet rejected, and because greedy always takes the heaviest admissible element, it never trades down. That is essentially an exchange/staying-ahead argument promoted to full generality.

Applied to the graphic matroid (forests of a graph), this theorem instantly proves Kruskal's MST algorithm optimal — you get the cut-property correctness for free as a special case. Its real value is diagnostic: to know whether a greedy idea is safe, you can ask 'do the feasible sets form a matroid?' instead of crafting a bespoke proof. The honest limits: many genuinely greedy problems (interval scheduling for the maximum number of jobs, Huffman coding) are not naturally matroids and still need their own exchange arguments, and the theorem assumes you want a maximum-weight independent set, not some other objective. It is a powerful sufficient condition, not a universal explanation of all greed.