# Proving NP-complete problem

Suppose the following problem:

Given an undirected graph G=(V,E), is it possible to choose a subset V' of vertex set V, such that deleting it removes all triangles (cycles of length 3), where |V'| is at most k?

How can I construct a reduction from vertex cover problem into such problem?

• Sorry, I missed the following info. You're supposed to choose V' such that it removes all triangles (cycle of length 3) – Ted Nov 12 '17 at 21:59

For every edge $(e_1, e_2)$ in the original VC instance, put edges $(e_1, e_2)$, $(e_1, e_{12})$ and $(e_{12}, e_2)$ in the graph of the instance of your problem.
<= : given a set of nodes breaking all triangles in the new instance of your problem, for all nodes of the form $e_{ij}$ included in the set, replace it by $e_i$ or $e_j$. The resulting set of nodes will cover all edges in the original graph.