Bounded-arity Boolean constraints become binary graph constraints

Keep one shared vertex for each old variable. For each listed constraint $i$, add a private tuple vertex $z_i$; for each occurrence $j=1,\dots ,k_i$, add a separate edge from $z_i$ to $x_{i,j}$ with relation $S_{i,j}=\{(T(a),B(b)):a\in \{0,1{\}}^q,(a_1,\dots ,a_{k_i})\in R_i,b=a_j\}$. Thus suffix coordinates after $k_i$ are ignored, and the graph has exactly ${\sum }_i{k}_i\le qm$ edge records.

If $\sigma$ satisfies the input, label each old vertex $x$ by $B(\sigma (x))$ and label $z_i$ by $T(a_i)$, where $a_i$ has first $k_i$ coordinates $(\sigma (x_{i,1}),\dots ,\sigma (x_{i,k_i}))$ and zero suffix. Then $a_i$'s prefix lies in $R_i$, so every edge relation $S_{i,j}$ is satisfied. This proves perfect completeness.

For any output labeling, decode an old vertex carrying $B(b)$ as bit $b$, and decode any other old label as $0$. If an input constraint is violated by this decoded assignment, at least one edge in its star must fail: if all its star edges passed, their common tuple label would have an accepted $R_i$-prefix equal coordinate-by-coordinate to the decoded old labels, contradicting that violation. This argument also covers repeated variable occurrences (they use the same old label on distinct parallel edge records) and $R_i=\mathrm{\varnothing }$.

Distinct input constraints have disjoint edge stars because their tuple vertices are private, even when their variable tuples repeat. Thus every output labeling violates at least as many edges as its decoded input assignment violates constraints, hence at least $m\mathrm{UNSAT}(C)$. If $m>0$, the output has at most $qm$ edges, so its violated fraction is at least $\mathrm{UNSAT}(C)\mathrm{/}q$. If $m=0$, both systems have unsatisfaction zero by the empty-list convention, and the inequality still holds.