3SAT polynomial-time many-one reduces to CLIQUE

Construct a graph $G_{\phi }$ with one vertex $v_{jr}$ for each literal occurrence ${\mathrm{\ell }}_{jr}$ in clause $C_j$. Join $v_{jr}$ and $v_{j^{\mathrm{\prime }}{r}^{\mathrm{\prime }}}$ by an edge exactly when $j\mathrm{\ne }{j}^{\mathrm{\prime }}$ and the literals ${\mathrm{\ell }}_{jr}$ and ${\mathrm{\ell }}_{j^{\mathrm{\prime }}{r}^{\mathrm{\prime }}}$ are not complementary. Output the CLIQUE instance $(G_{\phi },m)$.

Assume that $\phi$ is satisfiable, and choose a satisfying assignment. For each clause $C_j$, pick one literal made true by that assignment and take the corresponding vertex of $G_{\phi }$. This gives $m$ chosen vertices, one from each clause. Two chosen literals cannot be complementary because one assignment cannot make a variable and its negation both true, so step 1.1 makes every chosen pair adjacent. Therefore the chosen vertices form an $m$-clique.

Assume conversely that $G_{\phi }$ has a clique $K$ of size $m$. By step 1.1, no two vertices from the same clause are adjacent, so $K$ contains exactly one vertex from each clause. Again by step 1.1, the literals represented by those vertices are pairwise noncomplementary. Assign truth values so that every chosen literal is true, and extend arbitrarily to variables not yet assigned. Then each clause contains its chosen true literal, so $\phi$ is satisfiable.

The graph $G_{\phi }$ has $3m$ vertices and at most $9m^2$ candidate edges, so the map in step 1.1 is computable in polynomial time. Steps 2.1 and 2.2 prove $\phi \in 3\text{-}SAT⟺(G_{\phi },m)\in CLIQUE\mathrm{.}$ By [L1] and [L2], this is a polynomial-time many-one reduction.