Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.

• For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).

• For each internal node:

if any of its children is not selected, then select this node.

How do I prove that this greedy strategy gives an optimal answer? That there is no vertex cover smaller in size than the one that the above algorithm produces?

We first observe the following: There is an optimal cover $C$, and no leaf is in $C$. This is true since in any optimal cover $X$ you can replace all leaves in $X$ with their parents, and you get a vertex cover which is not larger than $X$.

Now take any optimal cover $C$ that does not contain leaves. Since no leave is selected, all parents of the leaves have to be in $C$. In other words, $C$ coincides with the greedy cover on the leaves and their parents. Next, we take out all edges that have been covered already. We can now apply the same argument again: In the remaining tree, no leaf needs to be selected, but then their parents have to be selected. And this is exactly what the greedy algorithm does. (A vertex becomes a leaf iff all of its children are selected in the previous step.) We repeat this argument we determined a complete vertex cover.

StackExchange Computer Science Q#12177, answer score: 11