Source: Approximation Algorithms — Vijay Vazirani (pg-$8$, Q-$1.3$)
The problem claims to device a new $2$-approximation algorithm for cardinality vertex cover.
Let $G$ be a graph. Take the DFS-tree $\tau$ of $G$. Let $S$ be the set of all non-leaf vertices in $\tau$. Then clearly S is a vertex cover, as any non-tree edge connects a non-leaf vertex to another non-leaf vertex or a leaf vertex to a non-leaf vertex.
Now I need to show that $|mvc| \geq \frac{1}{2} |S|$, where $mvc$ stands for minimum vertex cover.
I can't seem to find a rigorous way of doing it, although it seems intuitive.
Once, this is established, this leads to: |our solution|= $2 \times \frac{1}{2}|S| \leq 2\times|mvc|= 2\times |OPT|$.
Best Answer
You may select for the root vertex any of its children (either leaf or non-leaf), and take this pair as the first edge. Then for every other non-leaf child select one of its own children, taking few more edges. Then for every non-leaf grandchild that was not selected by its parent select one of its own children. And so on. All these tree edges are independent, therefore every vertex cover (including minimum ones) contains at least one end of each edge. The number of selected tree edges is at least half of the number of non-leaf vertices in the DFS tree, because every non-leaf vertex is an end of one of the selected edges.