We reduce from vertex cover in cubic graphs [1]}, [2]} (VC-3). An instance \((G,K)\)  of VC-3 comprises a graph \(G=(V,E)\) , with vertex set \(V=\lbrace v_1, v_2, ..., v_n\rbrace \)  such that each vertex has degree 3, and a positive integer \(K\) . The problem is to determine whether there exists a set of vertices \(V^{\prime } \subseteq V\)  such that for every edge \(e \in E\)  at least one endpoint of \(e\)  is in \(V^{\prime }\) , where \(|V^{\prime }| \le K\) .
