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?

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

StackExchange Computer Science Q#159880, answer score: 2