= Solution
For a <connected graph> with at least one <edge>, run <depth-first search> and output the <set> $I$ of <internal vertices of a rooted tree> in its discovery <tree> $T$. Part (d) proves that $I$ is a <vertex cover>. It is also connected: every ancestor of an internal <vertex> is internal, so the <graph path> in $T$ from that <vertex> to the root stays inside $I$. The root is internal when $|V|\geq2$.
For the approximation guarantee, choose a maximum-size <proper matching in a rooted tree> $M$ of $T$, whose existence is supplied. It is used only in the analysis; the <algorithm> need not construct it. Since every matched <edge> uses two distinct <vertices>,
$$
|V|=2|M|+|U(M)|.
$$
By part (e), $|L(T)|\geq|U(M)|$. Therefore
$$
\boxed{|I|=|V|-|L(T)|\leq|V|-|U(M)|=2|M|\leq2\,\mathrm{OPT}.}
$$
The final inequality holds because every <vertex cover> of $G$, connected or otherwise, must use at least one distinct endpoint for each of the disjoint <edges> in $M\subseteq E(G)$. Thus this is a \b[2-<approximation algorithm> in $O(|V|+|E|)$ <time complexity>].
For completeness, a disconnected input needs a feasibility check: if two different <connected components of a graph> contain <edges>, no connected <vertex cover> can meet both. If exactly one component contains <edges>, run the construction on that component and ignore isolated <vertices>. If there are no <edges>, the empty <vertex cover> is optimal when an empty solution is permitted; if a nonempty connected solution is required, any single <vertex> is optimal for a nonempty input. These conventions cover the boundary cases omitted from the main approximation argument.
Back to article page
