Alphabet reduction controls explicit size and degree

Put $H=G\circ P$ and $A=A_{\mathrm{\Sigma }}(G)$, the arity-six conversion of $H$. If $E(G)\mathrm{\ne }\mathrm{\varnothing }$, then $H$ has $Mm$ constraints by [F2], where each $q_e$ is the size of the local gadget of edge $e$. Every edge circuit has at most $2\mathrm{\ell }+O(W^3)$ wires by [F4], so each $q_e\le Q_{\mathrm{\Sigma }}$ by [F5], and therefore $M$ divides $M_{\mathrm{\Sigma }}=\mathrm{lcm}(1,\dots ,Q_{\mathrm{\Sigma }})$. In particular $M\le M_{\mathrm{\Sigma }}$, a constant depending only on $\mathrm{\Sigma }$.

If $E(G)=\mathrm{\varnothing }$, then $H$ has no variables and no constraints by [F2], and the conversion of an empty system is an edgeless graph, so all three bounds in clauses 1--3 hold with $m=0$ and every vertex degree zero.

Assume $E(G)\mathrm{\ne }\mathrm{\varnothing }$. Each of the $Mm$ constraints of $H$ has arity at most six, so the conversion creates at most six edge records per constraint by [F6]. Hence $\mid E(A)\mid \le 6\mid E(H)\mid =6Mm\le 6M_{\mathrm{\Sigma }}m$, as asserted in clause 1.

The vertex set of $A$ consists of the vertices of $H$ together with one private tuple vertex per constraint of $H$ by [F6], so $\mid V(A)\mid =\mid V(H)\mid +Mm$. The block coordinates account for at most $2\mathrm{\ell }m$ coordinates, since each of the at most $2m$ nonisolated vertices contributes $\mathrm{\ell }$ coordinates by [F3]. By [F7], the edge-private auxiliary variables of one gadget number at most $q_{\max }$, giving $\mid V(H)\mid \le (2\mathrm{\ell }+q_{\max })m$. Therefore $\mid V(A)\mid \le (2\mathrm{\ell }+q_{\max }+M_{\mathrm{\Sigma }})m$ by step 1.1, proving clause 2.

Consider a vertex of $A$ that comes from a coordinate $x$ of a shared block $B_v$ of $H$. By [F3] this coordinate appears in the gadgets of exactly the edge records incident to $v$, and $v$ is incident to at most $d$ edge records by hypothesis. In one copy of the gadget of such an edge, the coordinate occurs in at most $q_e$ constraints, each of arity at most six, so at most $6q_e$ times; after the uniform duplication of [F2] it occurs at most $6q_e\cdot M\mathrm{/}{q}_e=6M\le 6M_{\mathrm{\Sigma }}$ times in that gadget. Summing over the at most $d$ incident records gives ${\mathrm{deg}}_A(x)\le 6M_{\mathrm{\Sigma }}d$.

A vertex of $A$ that comes from an edge-private auxiliary variable of $H$ belongs to the gadget of exactly one edge, so the same occurrence count gives degree at most $6M\le 6M_{\mathrm{\Sigma }}$; a private tuple vertex created by the conversion has one edge record per variable occurrence of its constraint, hence degree at most six by [F6]. Since $d\ge 1$ whenever $E(G)\mathrm{\ne }\mathrm{\varnothing }$, all these degrees are at most $6M_{\mathrm{\Sigma }}d$. This proves clause 3.

The determinism, polynomial running time and fixed output alphabet are inherited from the reduction $A_{\mathrm{\Sigma }}$ by [F1]; the edge and vertex counts of clauses 1 and 2 are polynomial in $m$ by steps 2.1 and 2.2, and all relation tables are the constant-size tables of the $66$-symbol conversion.

Clauses 1, 2, 3 and 4 hold: the edgeless case is step 1.2, the edge and vertex bounds are steps 2.1 and 2.2, the degree bound is steps 2.3 and 3.1, and uniformity is step 3.2. Every constant produced is a function of $\mathrm{\Sigma }$ and $d$ alone, namely $6M_{\mathrm{\Sigma }}$, $2\mathrm{\ell }+q_{\max }+M_{\mathrm{\Sigma }}$ and $6M_{\mathrm{\Sigma }}d$.