# Maximum Independent Set of a Tree using Greedy Algorithm

I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?

Code extract shown here:

Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G
S = union(S, {v})
remove v and its neighbors from G
return S


Would this algorithm work for trees? Why or why not?

## 1 Answer

Yes, it would work for trees (acyclic graphs in general).

You need to prove one thing. Let $$\ell$$ be a leaf in a tree. Then there exists a maximum independent set that contains $$\ell$$.

The proof sketch is as follows. Let $$S^*$$ be a maximum independent set and assume that $$\ell \notin S^*$$. Since it is maximum, the unique neighbor $$v$$ of $$\ell$$ is in $$S^*$$. Since $$v$$ is $$\ell$$'s only neighbor, we can create a new independent set $$S = S^* \setminus \{v\} \cup \{\ell\}$$ with the same size.

This proves that your code is correct. (Strictly speaking you also have to argue that you can put isolated vertices in $$S$$, but that's fine.)