Connected vertex cover

A vertex cover $C$ whose induced subgraph $G[C]$ is connected. The optimization problem minimizes $|C|$ subject to both conditions. A graph with edges in two distinct connected components of a graph has no connected vertex cover: covering each of these edges requires selected vertices in different components. Isolated vertices can be ignored when exactly one component contains all the edges. The edge-free case depends on whether the empty solution is admitted.

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.