 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|\ge 2$.

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,By part (e), $|L(T)|\ge |U(M)|$. ThereforeThe 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 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.