While studying the dynamic programing algorithm for the maximum independent set problem in trees I thought about the following simple alternative algorithm. I tried to prove it's correctness but I do not know how to attack the proof.The algorithm iteratively finds a two vertices $u,v$ of the tree which have maximum distance among all pairs of vertices, puts $u$ in the independent set and removes $u$ and its neighbor from the tree. This procedure is continued until no more vertices are in the tree.Does anybody have an idea how to prove that this indeed yields a maximum independent set?
Algorithm for maximum independent set in trees
algorithms;trees