Maximum Independent Set of a Tree using Greedy Algorithm

Question

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?

Answer 1

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.)