= Solution
Use the specified construction as a <polynomial-time many-one reduction> from <3-SAT>. There are $2n+3m$ vertices and $n+6m$ edges: one edge per variable pair, three edges per clause <triangle in a graph>, and three occurrence edges per clause. Any <vertex cover> must take at least one vertex from every variable pair and at least two from every clause triangle. Therefore every cover has at least $n+2m$ vertices.
Given a satisfying <Boolean valuation>, include the vertex corresponding to the true <Boolean literal> in each variable pair. In each clause choose a true occurrence and omit its clause vertex, including the other two. Every variable edge and triangle edge is covered. An occurrence edge with an included clause endpoint is covered automatically; the only omitted occurrence vertex is joined to the included true-literal vertex. This is a <vertex cover> with exactly $n+2m$ vertices.
Conversely, a cover of that size must use exactly one vertex in each variable pair and exactly two in each triangle. Declare a variable true precisely when its positive-literal vertex is included. Each clause has one omitted vertex. Its occurrence edge forces the corresponding literal vertex into the cover, so that literal is true. Every clause is therefore satisfied. Thus
$$
\boxed{\text{formula satisfiable}\iff\text{constructed graph has a cover of size }n+2m.}
$$
The construction and target size are polynomial in the input length. Since <3-SAT> is <NP-complete>, the decision problem is <NP-hard>. The usual “at most $k$” version has the same equivalence here because $n+2m$ is an unavoidable lower bound. More generally, a cover with fewer than $k\leq|V|$ vertices can be padded to exactly $k$. Verifying a proposed cover is polynomial, so the usual vertex-cover decision problem is also in <NP> and hence <NP-complete>.
Back to article page
