How to find the minimum vertex cover of a graph ?

general
,
1

I am trying to solve this problem SPOJ.com - Problem PT07X understood the question but

unable to figure out an algorithm.Any one help me in solving the problem.

2

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.DFS call at each child can be used to check this.