2 copy editing
| link

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

    Tweeted twitter.com/#!/StackCompSci/status/336707461320957952
1
source | link

proof of 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.

  1. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
  2. 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?