One fixed transformation has constant-factor growth

By [F9] the integer $t\ge t_0$ lies in the transformation domain, so by [F1] and [F2] the map $T$ sends finite ${\mathrm{\Sigma }}_{\star }$-graphs to finite ${\mathrm{\Sigma }}_{\star }$-graphs by $G\mapsto A_{{\mathrm{\Sigma }}_t}(R_t(G))$, with ${\mathrm{\Sigma }}_t$ a finite alphabet of size at least two; by [F3] the graph $R_t(G)$ has at most $C_t\mid E(G)\mid$ edge records and is edgeless when $G$ is edgeless, and by [F4] its degrees are at most $d_t$.

Let $M_{{\mathrm{\Sigma }}_t},{\mathrm{\ell }}_t,q_{\max ,t}$ be the constants attached to the alphabet ${\mathrm{\Sigma }}_t$ by [F6]–[F8], and set $C_E:=6M_{{\mathrm{\Sigma }}_t}{C}_t$, $C_V:=(2{\mathrm{\ell }}_t+q_{\max ,t}+M_{{\mathrm{\Sigma }}_t})C_t$ and $C_D:=6M_{{\mathrm{\Sigma }}_t}{d}_t$. These are constants depending only on ${\mathrm{\Sigma }}_{\star }$ and $t$, because ${\mathrm{\Sigma }}_t,d_t,C_t$ do by [F4] and [F5], while $M_{{\mathrm{\Sigma }}_t},{\mathrm{\ell }}_t,q_{\max ,t}$ do by their definition at the input alphabet ${\mathrm{\Sigma }}_t$.

Let $G$ be an arbitrary finite ${\mathrm{\Sigma }}_{\star }$-graph with $m=\mid E(G)\mid$ edge records. Applying [F6] with $\mathrm{\Sigma }:={\mathrm{\Sigma }}_t$ and $H:=R_t(G)$, which is a finite ${\mathrm{\Sigma }}_t$-graph by [F1]–[F3], gives $\mid E(T(G))\mid =\mid E(A_{{\mathrm{\Sigma }}_t}(R_t(G)))\mid \le 6M_{{\mathrm{\Sigma }}_t}\mid E(R_t(G))\mid \le 6M_{{\mathrm{\Sigma }}_t}{C}_{t}m=C_{E}m$, the last inequality using [F3].

Applying [F7] to the same input $H=R_t(G)$ gives $\mid V(T(G))\mid \le (2{\mathrm{\ell }}_t+q_{\max ,t}+M_{{\mathrm{\Sigma }}_t})\mid E(R_t(G))\mid \le (2{\mathrm{\ell }}_t+q_{\max ,t}+M_{{\mathrm{\Sigma }}_t})C_{t}m=C_{V}m$, again using the edge bound of [F3].

Applying [F8] to $H=R_t(G)$ with degree parameter $d=d_t$, which bounds the degrees of $R_t(G)$ by [F4], shows that every vertex of $T(G)=A_{{\mathrm{\Sigma }}_t}(R_t(G))$ has degree at most $6M_{{\mathrm{\Sigma }}_t}{d}_t=C_D$.

By [F5] the first stage computes $R_t(G)$ deterministically in time polynomial in the bit length of the explicit encoding of $G$, so the explicit encoding of $R_t(G)$ has polynomially bounded length; by [F8] the second stage computes $A_{{\mathrm{\Sigma }}_t}(R_t(G))$ deterministically in time polynomial in the bit length of that encoding. Composing the two deterministic polynomial-time algorithms exhibits a deterministic algorithm computing $T(G)$ in time polynomial in the bit length of the explicit encoding of $G$.

The graph $G$ was arbitrary, the constants $C_E,C_V,C_D$ depend only on ${\mathrm{\Sigma }}_{\star }$ and $t$ by step 1.2, and all three output bounds and the uniformity clause were established in steps 2.1–2.4; hence $T$ has the claimed constant-factor growth. If $G$ is edgeless, then $R_t(G)$ is edgeless by [F3], and [F6] and [F7] applied with $m^{\mathrm{\prime }}=0$ give $\mid E(T(G))\mid =0$ and $\mid V(T(G))\mid =0$: the output is the empty graph and all bounds hold as $0\le 0$.