Exercise 1.3 from Vijay Vazirani - 'Approximation Algorithms' asks:
Consider the following factor $2$ approximation algorithm for the cardinality vertex cover problem. Find a depth first search tree in the given graph, $G$, and output the set, say S, of all the nonleaf vertices of this tree. Show that S is indeed a vertex cover for $G$ and $|S| ≤ 2$ · $OPT$. Hint: Show that $G$ has a matching of size $|S|/2$.
$EDIT$: the hint originally reads as follows: 'Show that G has a matching of size |S|'. A counterexample to this is when G is a path of length $4$ - then the DFS tree $T = D$, and a maximum matching is of size $2$. I took this to be a misprint and assumed that $|S|/2$ is the number the hint meant to refer to. Now after reading fade2black's comment, he also has a counter example in which $S$ is not a cover of $G$. After thinking about this for a while, I now cannot see for what reason $|S|$ should always be a cover of $G$. What I thought was proof of this statement (my attempt at the first part of the question below), is actually proof that $S$ is always a cover of $T$. Any ideas? Am I missing something? Is this a misprint, or is this just a poorly formulated question?
My attempt:
Showing $S$ is a vertex cover of $G$: Assume not. Then there is at least one vertex $v \in G-S$, $s.t.$ $v$ is a leaf and not adjacent to any vertex in $S$. Then either $v$ is disconnected in $G$, or $v$ is adjacent to some other leaf in $G$. If $v$ is adjacent to some other leaf in $G$, this implies that $G = K_2$, in which case $S = \emptyset$ and selecting either of the two vertices on its own gives a vertex cover. Therefore, if $G \neq K_2$ and $G$ is connected, $v$ must be connected to some $w \in S$.
Showing that $|S| \leq 2 \cdot OPT$: Consider a $2$-colouring of the vertices in $S$. At least one of the colours will have been used to colour at least half of the vertices in $S$. Pick that colour, and for each vertex coloured by it, match exactly one of its incident edges. It follows that $G$ admits a matching of size $|S|/2$. Let $M$ be a maximal matching in $G$. Then $|S|/2 \leq |M|$. We know that the minimum cardinality vertex cover of $G$ can be bounded from below by $|M|$, i.e. $|M| \leq OPT$. Together this gives $|S|/2 \leq |M| \leq OPT$, which implies that $|S|/2 \leq OPT \implies |S| \leq 2 \cdot OPT$.
Im pretty happy with the logic behind my solution to the second part of the exercise (showing that $|S| \leq 2 \cdot OPT$), but I'm not sure if the first part is quite there - I think the logic needs a bit of work. Any suggestions?