Depth-first approximation for connected vertex cover ($|I|\le 2\mathrm{OPT}$)

For a nontrivial connected graph, return the internal vertices of a rooted tree in a depth-first search tree. Undirected depth-first search has only ancestor-descendant edges, so every edge meets an internal vertex; the internal vertices are connected along parent paths. For a maximum-size proper matching in a rooted tree $M$ of that tree, existence of which is assumed, $|I|=|V|-|L|\le |V|-|U(M)|=2|M|$. Every vertex cover has size at least $|M|$, proving the factor two. The implementation needs only depth-first search, hence linear time complexity; it does not compute the analysis matching in a graph.