# Connected Vertex Cover

I'm trying to prove the Connected Vertex Cover problem is NP-complete. That is given a graph $G=(V,E)$ and integer $k$, is there a subset $X$ of $V$ such that $|X|≤k$ and that for every edge $(u,v)\in E$ at least one of $u$ and $v$ are in $X$. Furthermore, the subgraph $G[X]$ induced by $X$ must be connected.

I know the structure of an NP-complete proof. But I have no idea what problem to reduce to connected vertex cover and how to go about it.

• Have you tried to reduce from (ordinary) vertex cover? – D.W. May 28 '18 at 21:50
• I don't see how I alter the input so that I can use Connected Vertex Cover. Clearly if G has a connected vertex cover, then it has a normal vertex cover. But if G has a vertex cover, there's no guarantee the subgraph induced by the vertex cover is connected. – CrossGuard May 28 '18 at 22:36
• Please don't delete your question after you've already gotten an answer. That is impolite to answerers, who are writing not only for your benefit but also for the benefit of anyone else who has the same question in the future. Thank you. – D.W. May 29 '18 at 20:06