**When does greedy work?**

Observe the following property of forests:

**Lemma**: Forests on a graph such that then such that is a forest.

**Proof**: Notice that cannot be a tree and so it has atleast two components. Let be the components of . We claim that all the edge of cannot be contained in since each is a tree on vertices. Since , there must be an edge and two components of , and such that and . Thus is still a forest.

**Matroids**

Let be a universe and be a collection of subsets of . We say that is a matroid if:

- .
- and .
- and such that .

A set is called *independent*. Notice that the set where is the set of all forests such that is a matroid.

Suppose is a matroid and we have a weight function and we want to find a maximum weight independent set. Consider the following greedy algorithm:

- Sort the elements of in decreasing order of their weight, so that .
- Initialize where is the first element such that .
- Iterate till you can no longer add any element while still remaining in .

**Theorem**: This algorithm gives us the maximum weight independent set in .

**Proof**: We first observe that the size of the set returned by the algorithm is the same as the size of , where is a maximum weight independent set in . Let the elements picked by greedy be in order. Let the elements of (in decreasing order of weight) be . Suppose greedy fails; then there exists a such that since otherwise since . We know that and . By the property of matroids, we get that there must be an element such that . Since which contradicts the choice of the greedy algorithm!

Notice that this same proof would have worked for proving the correctness of the greedy algorithm for finding a minimum (or maximum) weight spanning tree. Another example of matroid is , where is a set of vectors in and is a collection of all linearly independent subsets of . Thus the greedy algorithm would also work for finding a maximum weight linearly independent set of vectors.