the exchange property of matroids
Of the three axioms defining a matroid, two are easy bookkeeping — the empty set is independent, and subsets of independent sets are independent. The third is the engine that makes everything work, and it deserves to be understood on its own. It is the guarantee that a smaller independent set can always 'grow toward' a larger one by borrowing a single element.
The exchange property (also called the augmentation axiom) states: if A and B are both independent sets and A has strictly fewer elements than B, then there exists some element x in B but not in A such that A together with x is still independent. In words, whenever you are independent but smaller than another independent set, you can add one of the larger set's elements without losing independence. Two consequences flow directly. First, every maximal independent set has the same size: if two bases differed in size, the smaller could be augmented from the larger and so would not be maximal — contradiction. That common size is the rank. Second, this is precisely the property a 'greedy stays ahead' argument needs: it lets greedy, whenever it is behind in size, always find a fresh admissible element to take, which is the heart of the matroid-greedy theorem's proof. In the graphic matroid this is geometrically obvious — a forest with fewer edges than a larger forest must have more separate trees, so some edge of the larger forest joins two of the smaller forest's components without making a cycle.
Understanding this one axiom demystifies why matroids and greed fit together: the exchange property IS the abstract version of the swap-without-loss move at the center of every greedy correctness proof. And its failure is equally diagnostic. The feasible sets of 0/1 knapsack (subsets whose total weight fits the capacity) violate it — you can have a small light set and a larger set where no single element of the larger one can be added to the small set without overflowing — which is exactly why no clean greedy rule is optimal for that problem.
Vectors in the plane: A = {(1,0)} (size 1, independent), B = {(1,1), (0,1)} (size 2, independent). A is smaller, so the exchange property promises some vector of B extends A independently — indeed (0,1) is not a multiple of (1,0), so {(1,0),(0,1)} is independent. Try this in 0/1 knapsack's feasible sets and it can fail.
The exchange property lets a smaller independent set borrow an element from a larger one — the abstract heart of every greedy swap proof.
Where the exchange property fails, no clean greedy rule is universally optimal. The feasible sets of 0/1 knapsack violate it, which is the structural reason greedy breaks there.