Recall that 3SAT is a known NP-complete problem, and NP-completeness is preserved under polynomial-time reductions.

Consider how to represent each clause and variable in 3SAT as a graph structure where edges encode logical constraints.

Construct a polynomial-time reduction from 3SAT to CLIQUE by designing a graph where a clique of size *k* exists if and only if the original 3SAT formula is satisfiable.