We can show that the clique problem is NP-hard by proving that

Answer: None of the above. To show the clique problem is NP-hard you must reduce a known NP-hard problem to CLIQUE (i.e., show some NP-hard problem ≤_P CLIQUE). The options given all state reductions in the opposite direction (CLIQUE ≤_P other_problem), which does not establish clique's NP-hardness.

• Example 1 — 3-CNF-SAT ≤_P CLIQUE (sketch):

  For each clause create a node for each literal; connect nodes from different clauses when the literals are not contradictory. A clique of size equal to the number of clauses corresponds to choosing one compatible literal per clause, which yields a satisfying assignment. This gives a polynomial-time reduction from 3-CNF-SAT to CLIQUE.

• Example 2 — VERTEX_COVER ≤_P CLIQUE (complement construction):

  Given an instance (G, k) of vertex cover with n vertices, form the complement graph G'. Let k' = n − k. Then G has a vertex cover of size k if and only if G' has a clique of size k'. Thus mapping (G, k) to (G', k') is a polynomial-time reduction from VERTEX_COVER to CLIQUE.

Why the listed options are incorrect: each option presents a reduction from CLIQUE to another problem. Such a reduction would show the other problem is at least as hard as clique, but it does not show clique is NP-hard. To prove clique is NP-hard you must reduce a known NP-hard problem into CLIQUE.