X_2^k, X_3^k$ to represent the literals. If $x_{\ell_p}$ is the variable $v_i$, then we choose as $X_p^k$ a vertex from row $i$ and column $p$, and choose the true vertex if the literal is positive and the false vertex if the literal is a negated variable. For $p \in \{4,\ldots,8\}$, let $Y_p^k$ be the true vertex from the $(p-3)$th row and $p$th column of the clause block ${\mathcal C}^{k,k}$. Finally add the ten edges $\{ X_1^kY_4^k, X_2^kY_5^k, X_2^kY_8^k, X_3^kY_6^k, X_3^kY_7^k, Y_4^kY_5^k, Y_4^kY_6^k, Y_5^kY_7^k, Y_6^kY_8^k, Y_7^kY_8^k\}$ so that $\{X_1^k,X_2^k,X_3^k, Y_4^k, Y_5^k,Y_6^k,Y_7^k,Y_6^k\}$ induces the constraint graph $J$.

=\[circle,draw=black, fill=black, minimum size=5pt, inner sep=1pt\] =\[draw,black\]

We now define the graph $H_\phi$. It contains:

-   the disjoint union of clause graphs ${\mathcal C}^k$, $1 \leq k \leq m$ (we think of the clause graphs as being arranged side-by-side, so that they form an array of $n+5m+1$ rows and $8m$ columns),

-   edges from each true vertex of each clause graph to each false vertex in the same row of other clause graphs, and

-   an additional vertex $v_0$ joined to each vertex in the dominating block of each clause graph.

Note that each column of $H_\phi$ contains exactly one vertex that is in a 