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?