$\mathbb{P}[x\in\mathcal{U}]\leq\binom{n}{\varepsilon_{1}n}(1/2+\varepsilon)^{n-\varepsilon_{1}n}<2^{-n+20\varepsilon
n}.$ (9.2)

It follows that $\mathbb{E}[|\mathcal{U}|]<2^{n}2^{-n+20\varepsilon
n}=2^{20\varepsilon n}$. Therefore, by Markov’s inequality we have that

$\mathbb{P}[|\mathcal{U}|\geq 2^{\varepsilon_{2}n}]<2^{20\varepsilon
n}/2^{\varepsilon_{2}n}<2^{-\varepsilon_{2}n/2},$

so a.a.s. $|\mathcal{U}|\leq 2^{\varepsilon_{2}n}$. $(\mathrm{R}1)$ holds
trivially by the choice of $\mathcal{U}$. Furthermore, we have that

$\Bigg{|}\bigcup_{i\in[4]}B^{s+\ell}_{\mathcal{Q}^{n}}(x_{i})\Bigg{|}\leq
5n^{s+\ell},$

so, by (9.2) and a union bound, $(\mathrm{R}5)$ also holds a.a.s.

To see that $(\mathrm{R}2)$ holds, fix $x\in V(\mathcal{Q}^{n})$ and $y\in
B^{s+5\ell}_{\mathcal{Q}^{n}}(x)$. Then,
$\mathbb{E}[d_{G-\\{x\\}}(y)]=(1/2-\varepsilon)n\pm 1$. Thus, by Lemma 4.2,

$\mathbb{P}[d_{G-\\{x\\}}(y)\leq\gamma n-1]\leq 2^{-n/20}.$

Therefore, by (9.2), we have that $\mathbb{P}[x\in\mathcal{U}\wedge
d_{G-\\{x\\}}(y)\leq\gamma n-1]\leq 2^{-n+20\varepsilon n-n/20}\leq
2^{-31n/30}$. A union bound over all $x\in V(\mathcal{Q}^{n})$ and over all
$y\in B^{s+5\ell}_{\mathcal{Q}^{n}}(x)$ shows that $(\mathrm{R}2)$ holds
a.a.s.

The fact that $(\mathrm{R}3)$ holds a.a.s. can be shown similarly.

Finally, consider $(\mathrm{R}4)$. Let $x\in V(\mathcal{Q}^{n})$, and suppose
$x\in V(L)$, for some layer $L$. First, let $a,b\in\mathcal{D}(L)$ be
distinct. We are going to show that a.a.s. we can find the desired collection
of $(x,a,b)$-consistent systems of paths.

Recall that an $(x,a,b)$-consistent system of paths $(P_{1},\ldots,P_{6})$, as
defined in Section 9.1, is determined uniquely by a $6$-tuple of directions
$(c,d,d_{1},d_{2},d_{3},d_{4})$. In order to show that
$(\mathrm{R}4)$$(\mathrm{R}4.\mathrm{I})$ is satisfied, we will first consider
the directions $c$ and $d$, and then the rest of the tuple. Recall that all
$(x,a,b)$-consistent systems of paths contain the two edges $\\{x,x+a\\}$ and
$\\{x,x+b\\}$. Then, once $c$ and $d$ are fixed, this determines a total of
$6$ more edges. The remaining $8$ edges will be determined by the choice of
$(d_{1},d_{2},d_{3},d_{4})$.

Consider a collection $\mathcal{W}$ of disjoint pairs of distinct directions
$(c,d)$ with $c,d\in\mathcal{D}(L)\setminus\\{a,b\\}$ such that
$|\mathcal{W}|\geq n/4$. For each $(c,d)\in\mathcal{W}$, let
$E^{*}(c,d)\subseteq E(\mathcal{Q}^{n})$ be the set of six edges of an
$(x,a,b)$-consistent system of paths determined by these two directions.
Observe that, since the pairs in $\mathcal{W}$ are disjoint, it follows that,
for any distinct $(c,d),(c^{\prime},d^{\prime})\in\mathcal{W}$, we have
$E^{*}(c,d)\cap E^{*}(c^{\prime},d^{\prime})=\varnothing$. Now let
$\mathcal{W}_{G}\coloneqq\\{(c,d)\in\mathcal{W}:E^{*}(c,d)\subseteq E(G)\\}$
and $X\coloneqq|\mathcal{W}_{G}|$. We have that
$\mathbb{E}[X]\geq(1/2-\varepsilon)^{6}n/4$ and, by Lemma 4.2, it follows that
$\mathbb{P}[X\leq\gamma n]\leq 2^{-\gamma n}$.

For each $(c,d)\in\mathcal{W}$, let $\mathcal{V}(c,d)$ be a collection of
disjoint $4$-tuples of distinct directions $(d_{1},d_{2},d_{3},d_{4})$ with
$d_{1},d_{2},d_{3},d_{4}\in\mathcal{D}(L)\setminus\\{a,b,c,d\\}$ such that
$|\mathcal{V}(c,d)|\geq n/5$. For each
$(d_{1},d_{2},d_{3},d_{4})\in\mathcal{V}(c,d)$, let
$E^{*}(c,d,d_{1},d_{2},d_{3},d_{4})\subseteq E(\mathcal{Q}^{n})$ be the set of
eight edges of an $(x,a,b)$-consistent system of paths determined by
$(c,d,d_{1},d_{2},d_{3},d_{4})$ which are not in
$E^{*}(c,d)\cup\\{\\{x,x+a\\},\\{x,x+b\\}\\}$. In particular, since the tuples
in $\mathcal{V}(c,d)$ are disjoint, it follows that, for any distinct
$(d_{1},d_{2},d_{3},d_{4}),(d_{1}^{\prime},d_{2}^{\prime},d_{3}^{\prime},d_{4}^{\prime})\in\mathcal{V}(c,d)$,
we have $E^{*}(c,d,d_{1},d_{2},d_{3},d_{4})\cap
E^{*}(c,d,d_{1}^{\prime},d_{2}^{\prime},d_{3}^{\prime},d_{4}^{\prime})=\varnothing$.
Now let
$\mathcal{V}_{G}(c,d)\coloneqq\\{(d_{1},d_{2},d_{3},d_{4})\in\mathcal{V}(c,d):E^{*}(c,d,d_{1},d_{2},d_{3},d_{4})\subseteq
E(G)\\}$, and let $Y(c,d)\coloneqq|\mathcal{V}_{G}(c,d)|$. We then have that
$\mathbb{E}[Y(c,d)]\geq(1/2-\varepsilon)^{8}n/5$ and, again by Lemma 4.2, it
follows that $\mathbb{P}[Y(c,d)\leq\gamma n]\leq 2^{-\gamma n}$. Thus, by a
union bound, with probability at least $1-2^{-\gamma n/2}$, for every
$(c,d)\in\mathcal{W}$ we have $Y(c,d)\geq\gamma n$.

Let $\mathcal{E}(x,a,b)$ be the event that
$G\cup\\{\\{x,x+a\\},\\{x,x+b\\}\\}$ contains a collection
$\mathfrak{C}(x,a,b)$ of $(x,a,b)$-consistent systems of paths satisfying
$(\mathrm{R}4)$$(\mathrm{R}4.\mathrm{I})$. By combining all the above, it
follows that

$\mathbb{P}[\mathcal{E}(x,a,b)]\geq 1-2^{-\gamma n/4}.$ (9.3)

The same bound can be proved for the cases where
$a\notin\mathcal{D}(L),b\in\mathcal{D}(L)$ and $a,b\notin\mathcal{D}(L)$.
Observe that, for any $x\in V(\mathcal{Q}^{n})$ and
$a,b\in\mathcal{D}(\mathcal{Q}^{n})$, the event $\mathcal{E}(x,a,b)$ is
independent of the event that $x\in\mathcal{U}$. Now, by combining (9.3) with
(9.2) and a union bound over all choices of
$a,b\in\mathcal{D}(\mathcal{Q}^{n})$, and then a union bound over all $x\in
V(\mathcal{Q}^{n})$, we conclude that $(\mathrm{R}4)$ holds a.a.s.

The proof of (ii) is similar. Let $H\subseteq\mathcal{Q}^{n}$ be given and
consider a random partition of $E(H)$ into $r$ parts $H_{1},\dots,H_{r}$, in
such a way that each edge is assigned to one of the parts uniformly and
independently of all other edges. For each $x\in
V(\mathcal{Q}^{n})\setminus\mathcal{U}$, let $\mathcal{B}(x)$ be the event
that there exists some $i\in[r]$ such that $d_{H_{i}}(x)<d_{H}(x)/(2r)$.
Observe that, if $\overline{\mathcal{B}(x)}$ holds for all $x\in
V(\mathcal{Q}^{n})\setminus\mathcal{U}$, then no vertex outside $\mathcal{U}$
will be contained in $\mathcal{U}(H_{i},\varepsilon_{1}/(2r))$ for any
$i\in[r]$. It would then follow that $(\mathrm{R}1)$, $(\mathrm{R}2)$,
$(\mathrm{R}3)$ and $(\mathrm{R}5)$ all hold with the desired constants for
each $H_{i}$. Fix $x\in V(\mathcal{Q}^{n})\setminus\mathcal{U}$ and $i\in[r]$.
Let $X\coloneqq d_{H_{i}}(x)$. Then,
$\mathbb{E}[X]=d_{H}(x)/r\geq\varepsilon_{1}n/r$. Thus, by Lemma 4.2,
$\mathbb{P}[X\leq\mathbb{E}[X]/2]\leq e^{-\varepsilon_{1}^{2}n}$. A union
bound over all $i\in[r]$ shows that $\mathbb{P}[\mathcal{B}(x)]\leq
re^{-\varepsilon_{1}^{2}n}\leq e^{-\varepsilon_{1}^{3}n}$.

We now consider the property $(\mathrm{R}4)$. For each $x\in\mathcal{U}$, let
$\mathcal{B}(x)$ be the event that there exist $i\in[r]$ and distinct
directions $a,b\in\mathcal{D}(\mathcal{Q}^{n})$ such that $(\mathrm{R}4)$ does
not hold for $H_{i}$ with $\gamma/r^{10}$ playing the role of $\gamma$.

Fix $x\in\mathcal{U}$, $i\in[r]$ and distinct directions
$a,b\in\mathcal{D}(\mathcal{Q}^{n})$. Similarly as in (i), using Lemma 4.2 one
can show that the probability that $H_{i}$ does not satisfy $(\mathrm{R}4)$
for $x$ with $\gamma/r^{10}$ playing the role of $\gamma$ is at most
$2^{-\gamma^{2}n}+2^{-\gamma^{3}n}$. Therefore, by a union bound over all
choices of $a,b\in\mathcal{D}(\mathcal{Q}^{n})$ and over each $i\in[r]$, we
have that $\mathbb{P}[\mathcal{B}(x)]\leq
rn^{2}(2^{-\gamma^{2}n}+2^{-\gamma^{3}n})\leq e^{-\varepsilon_{1}^{3}n}$.

Finally, we are interested in the event where $\mathcal{B}(x)$ does not occur
for any $x\in V(\mathcal{Q}^{n})$. We will invoke Lemma 4.8. Note that each
event $\mathcal{B}(x)$ is mutually independent of all but at most $n^{10}$
other events. We have that $\mathbb{P}[\mathcal{B}(x)]\leq
e^{-\varepsilon_{1}^{3}n}$ for every $x\in V(\mathcal{Q}^{n})$ and $e\cdot
e^{-\varepsilon_{1}^{3}n}(n^{10}+1)<1$, so by Lemma 4.8 there exists an edge-
decomposition of $H$ with the desired properties. ∎

Finally, we need to show a result analogous to Lemma 8.5 for robust graphs,
that is, that scant molecules are not too clustered. Recall that
$\mathit{Res}(\mathcal{Q}^{n},\delta)$ was defined in Section 7.1.

######  Lemma 9.5.

Let $0<1/n\ll 1/C\ll\varepsilon_{1},\varepsilon_{2}\ll\gamma,\delta\leq 1$ and
$1/n\ll 1/s\leq 1/\ell$, where $n,C,s,\ell\in\mathbb{N}$. Let
$H\subseteq\mathcal{Q}^{n}$ and $\mathcal{U}\subseteq V(\mathcal{Q}^{n})$ be
such that $H$ is
$(s,\ell,\varepsilon_{1},\varepsilon_{2},\gamma,\mathcal{U})$-robust. Let
$\mathcal{U}_{I}\subseteq V(I)$ be the set of vertices $u\in V(I)$ such that
$\mathcal{U}$ contains some clone of $u$. For each $v\in V(I)$ and each
$i\in[2^{s}]$, let $v_{i}$ be the $i$-th clone of $v$, and let
$\mathcal{M}_{v}\coloneqq\\{v_{i}:i\in[2^{s}]\\}$. Let
$R\sim\mathit{Res}(I,\delta)$ and, for each $i\in[2^{s}]$, let $R_{i}$ be the
$i$-th clone of $R$. Let

$B\coloneqq\\{v\in V(I):\text{there exists }i\in[2^{s}]\text{ with
}v_{i}\notin\mathcal{U}\text{ and }e_{H}(v_{i},R_{i})<\varepsilon_{1}\delta
n/4\\}.$

Let $\mathcal{E}_{1}$ be the event that there exists some $u\in V(I)$ such
that $|B_{I}^{10\ell}(u)\cap B|\geq C$. Let $\mathcal{E}_{2}$ be the event
that there exists some $u\in\mathcal{U}_{I}$ such that $|B_{I}^{5\ell}(u)\cap
B|\geq 1$. Then, $\mathbb{P}[\mathcal{E}_{1}\vee\mathcal{E}_{2}]\leq 1/n$.

###### Proof.

Let $u\in V(I)$ and let $D\subseteq B_{I}^{10\ell}(u)\setminus\mathcal{U}_{I}$
be a set of $C$ vertices. Let $D^{\prime}\coloneqq\bigcup_{x,y\in D:x\neq
y}N_{I}(x)\cap N_{I}(y)$. Since any pair of distinct vertices in $I$ share at
most two neighbours, we have that $|D^{\prime}|\leq 2\binom{C}{2}$. For each
$i\in[2^{s}]$, we denote the $i$-th clone of $D^{\prime}$ by $D^{\prime}_{i}$,
and let $R^{\prime}_{i}\coloneqq R_{i}\setminus D^{\prime}_{i}$.

For each $x\in V(\mathcal{Q}^{n})$, let $i(x)$ be the unique index
$i\in[2^{s}]$ such that $x\in V(L_{i})$. Observe that, by $(\mathrm{R}1)$, we
have $e_{H}(x,V(L_{i(x)}))>2\varepsilon_{1}n/3$ for every $x\in
V(\mathcal{Q}^{n})\setminus\mathcal{U}$. For each $x\in V(\mathcal{Q}^{n})$,
let $\mathcal{E}_{x}$ be the event that
$e_{H}(x,R_{i(x)})\leq\varepsilon_{1}\delta n/4$, and let
$\mathcal{E}^{\prime}_{x}$ be the event that
$e_{H}(x,R^{\prime}_{i(x)})\leq\varepsilon_{1}\delta n/4$. It follows by Lemma
4.2 that $\mathbb{P}[\mathcal{E}^{\prime}_{x}]\leq e^{-\varepsilon_{1}\delta
n/16}$ for all $x\in V(\mathcal{Q}^{n})\setminus\mathcal{U}$. For each $v\in
V(I)$, let $\mathcal{E}_{v}$ and $\mathcal{E}_{v}^{\prime}$ be the events that
there exists $i\in[2^{s}]$ with $v_{i}\notin\mathcal{U}$ such that
$\mathcal{E}_{v_{i}}$ and $\mathcal{E}_{v_{i}}^{\prime}$ hold, respectively.
By a union bound, it follows that $\mathbb{P}[\mathcal{E}_{v}^{\prime}]\leq
2^{s}e^{-\varepsilon_{1}\delta n/16}$ for all $v\in V(I)$. Finally, let
$\mathcal{E}_{D}$ and $\mathcal{E}^{\prime}_{D}$ be the events that
$\mathcal{E}_{v}$ and $\mathcal{E}_{v}^{\prime}$, respectively, hold for every
$v\in D$. Note that the events in the collection
$\\{\mathcal{E}_{v}^{\prime}:v\in V(I)\\}$ are mutually independent.
Furthermore, since the event $\mathcal{E}_{x}$ implies
$\mathcal{E}_{x}^{\prime}$ for all $x\in V(\mathcal{Q}^{n})$, we have that

$\mathbb{P}[\mathcal{E}_{D}]\leq\mathbb{P}[\mathcal{E}^{\prime}_{D}]\leq(2^{s}e^{-\varepsilon_{1}\delta
n/16})^{C}<e^{-5n}.$

By a union bound over all $u\in V(I)$ and over all choices of $D$, we have
$\mathbb{P}[\mathcal{E}_{1}]\leq e^{-n}$.

Consider now any $u\in\mathcal{U}_{I}$. Observe that, if $v\in
B_{I}^{5\ell}(u)$, then for every $i,j\in[2^{s}]$ we have that ${\rm
dist}(u_{i},v_{j})\leq 5\ell+s$. Therefore, by $(\mathrm{R}2)$, for all $v\in
B_{I}^{5\ell}(u)$ and $i\in[2^{s}]$ such that $v_{i}\notin\mathcal{U}$, we
have $d_{H}(v_{i})\geq\gamma n$. For each $v\in B_{I}^{5\ell}(u)$ and each
$i\in[2^{s}]$ with $v_{i}\notin\mathcal{U}$, let $\mathcal{F}_{v_{i}}$ be the
event that $e_{H}(v_{i},R_{i})\leq\varepsilon_{1}\delta n/4$, and let
$\mathcal{F}_{v}$ be the event that there exists some $i\in[2^{s}]$ with
$v_{i}\notin\mathcal{U}$ such that $\mathcal{F}_{v_{i}}$ holds. By Lemma 4.2
and a union bound, it follows that $\mathbb{P}[\mathcal{F}_{v}]\leq
2^{-\gamma\delta n/16}$. Then, by a union bound over all $u\in\mathcal{U}_{I}$
and $v\in B_{I}^{5\ell}(u)$,

$\mathbb{P}[\mathcal{E}_{2}]\leq|\mathcal{U}_{I}|\cdot|B^{5\ell}_{I}(\mathcal{U}_{I})|\cdot\mathbb{P}[\mathcal{F}_{v}]\leq
2n^{5\ell}2^{\varepsilon_{2}n}2^{-\gamma\delta n/16}.\qed$

###  9.3. Hamilton cycles in robust subgraphs of the cube

It will be useful to prove the following result, which (together with Lemma
9.4) directly implies the case $k=2$ of Theorem 1.8 (by choosing $H$ in
Theorem 1.8 to play the role of $H^{\prime}$ in Theorem 9.6 and $F$ to be
empty). As with Theorem 8.1, the formulation of Theorem 9.6 is designed so
that the case $k>2$ can be derived easily (see Section 9.4). To state the
result, we need the following notation.

Given any integers $s\leq n$, we say that $d\in\mathcal{D}(\mathcal{Q}^{n})$
is an _$s$ -direction_ if, for any $x\in V(\mathcal{Q}^{n})$, $x$ and $x+d$
differ only by one of the first $s$ coordinates. Given a graph
$F\subseteq\mathcal{Q}^{n}$, a set $\mathcal{U}\subseteq V(\mathcal{Q}^{n})$
and $\ell,s\in\mathbb{N}$, we say that $F$ is _$(\mathcal{U},\ell,s)$ -good_
if, for each $x\in\mathcal{U}$, the set $E_{F}(x)\coloneqq\\{e\in E(F):e\cap
N_{\mathcal{Q}^{n}}(x)\neq\varnothing\\}$ satisfies that, for each
$d\in\mathcal{D}(\mathcal{Q}^{n})$ which is not an $s$-direction, we have
$|\\{e\in E_{F}(x):\mathcal{D}(e)=d\\}|\leq n/\ell$. Thus, a graph is good if
locally the directions of its edges are not too correlated (ignoring
$s$-directions). The goodness of the ‘forbidden’ graph $F$ below will be
needed when finding the special absorbing structures (see Step 11).

######  Theorem 9.6.

Let $0<1/\ell\ll\varepsilon_{1}\ll\varepsilon_{2}\ll\gamma\leq 1$ and
$1/\ell\ll\eta,1/c\leq 1$, with $\ell\in\mathbb{N}$. Let $s\coloneqq 10\ell$
and $n\in\mathbb{N}$. Then, there exists $\Phi\in\mathbb{N}$ such that the
following holds.

Let $H\subseteq\mathcal{Q}^{n}$ and $\mathcal{U}\subseteq V(\mathcal{Q}^{n})$
be such that $H$ is an
$(s,\ell,\varepsilon_{1},\varepsilon_{2},\gamma,\mathcal{U})$-robust subgraph,
and let $Q\sim\mathcal{Q}^{n}_{\eta}$. Then, a.a.s. there is a
$(\mathcal{U},\ell^{2},s)$-good subgraph $Q^{\prime}\subseteq Q$ with
$\Delta(Q^{\prime})\leq\Phi$ such that

  * •

for every $H^{\prime}\subseteq\mathcal{Q}^{n}$, where $d_{H^{\prime}}(x)\geq
2$ for every $x\in\mathcal{U}$, and

  * •

for every $F\subseteq\mathcal{Q}^{n}$ with $\Delta(F)\leq c\Phi$ which is
$(\mathcal{U},\ell,s)$-good,

we have that $((H\cup Q)\setminus F)\cup H^{\prime}\cup Q^{\prime}$ contains a
$(\mathcal{U},\ell^{2},s)$-good Hamilton cycle $C$ such that, for all
$x\in\mathcal{U}$, both edges of $C$ incident to $x$ belong to $H^{\prime}$.

As we have already discussed, the proof of Theorem 9.6 builds on that of
Theorem 8.1. Thus, we will avoid repeating all the details which are
analogous, and we will often refer back the proof of Theorem 8.1. A full
sequential proof can be found in [28].

###### Proof of Theorem 9.6.

Let $1/D,\delta^{\prime}\ll 1$, let
$\varepsilon_{1}\ll\varepsilon_{2}\ll\gamma,\delta^{\prime}\leq 1$, and let

$0<1/n_{0}\ll\delta,\lambda\ll 1/\ell\ll
1/k^{*},\alpha^{\prime}\ll\beta,1/S^{\prime}\ll
1/c,1/D,\eta,\varepsilon_{1},\delta^{\prime},$

where $n_{0},\ell,k^{*},S^{\prime},D\in\mathbb{N}$. Our proof assumes that $n$
tends to infinity; in particular, $n\geq n_{0}$. Let $\Phi\coloneqq
60\ell^{4}$ and $\Psi\coloneqq c\Phi$.

We define the layers $L_{1},\dots,L_{2^{s}}$ of $\mathcal{Q}^{n}$, the
intersection graph $I$ and, for each $G\subseteq\mathcal{Q}^{n}$, the graphs
$I(G)$ and $G_{I}$ as in the proof of Theorem 8.1. Similarly, for any layer
$L$ and $\mathcal{G}\subseteq I$, we keep the notation $\mathcal{G}_{L}$ for
the clone of $\mathcal{G}$ in $L$.

Let $\mathcal{U}$ be as in the statement of Theorem 9.6. In particular,
$\mathcal{U}(H,\varepsilon_{1})\subseteq\mathcal{U}$ by $(\mathrm{R}1)$. Let
$\mathcal{U}_{I}\subseteq V(I)$ be the set of vertices $x\in V(I)$ such that
there is some clone $x^{\prime}$ of $x$ with $x^{\prime}\in\mathcal{U}$. Note
that, by property $(\mathrm{R}2)$, for each $x\in\mathcal{U}_{I}$, there is
exactly one clone $x^{\prime}$ of $x$ with $x^{\prime}\in\mathcal{U}$.

For each $i\in[8]$, let $\eta_{i}\coloneqq\eta/8$ and
$G_{i}\sim\mathcal{Q}^{n}_{\eta_{i}}$, where these graphs are chosen
independently. We have that
$\bigcup_{i=1}^{8}G_{i}\sim\mathcal{Q}^{n}_{\eta^{\prime}}$ for some
$\eta^{\prime}<\eta$, so it suffices to show that a.a.s. there is a
$(\mathcal{U},\ell^{2},s)$-good subgraph
$Q^{\prime}\subseteq\bigcup_{i=1}^{8}G_{i}$ with $\Delta(Q^{\prime})\leq\Phi$
and such that, for every $H^{\prime}\subseteq\mathcal{Q}^{n}$, where
$d_{H^{\prime}}(x)\geq 2$ for every $x\in\mathcal{U}$, and every
$F\subseteq\mathcal{Q}^{n}$ with $\Delta(F)\leq\Psi$ which is
$(\mathcal{U},\ell,s)$-good, the graph
$((H\cup\bigcup_{i=1}^{8}G_{i})\setminus F)\cup H^{\prime}\cup Q^{\prime}$
contains a Hamilton cycle of the form in the statement of the theorem. We now
split our proof into several steps.

Step 1. Finding a tree and a reservoir. As in the proof of Theorem 8.1,
consider the probability space
$\Omega\coloneqq\mathcal{Q}^{n-s}_{\eta_{1}^{2^{s}}}\times\mathit{Res}(\mathcal{Q}^{n-s},\delta^{\prime})$
and let $R\sim\mathit{Res}(I,\delta^{\prime})$. Let $\mathcal{E}_{1}$ be the
event that there exists a tree $T\subseteq I(G_{1})-(R\cup
B^{5}_{I}(\mathcal{U}_{I}))$ such that the following hold:

  1. $(\mathrm{TR}1)$

$\Delta(T)<D$, and

  2. $(\mathrm{TR}2)$

for all $x\in V(I)\setminus B^{5}_{I}(\mathcal{U}_{I})$, we have that
$|N_{I}(x)\cap V(T)|\geq 4(n-s)/5$.

Note that, by $(\mathrm{R}3)$, for all $x,y\in\mathcal{U}_{I}$ we have that
${\rm dist}(x,y)\geq\gamma n/2$. Furthermore, by $(\mathrm{R}5)$, we have
that, if we see $x_{1}\coloneqq\\{0\\}^{n-s}$, $x_{2}\coloneqq\\{1\\}^{n-s}$,
$x_{3}\coloneqq\\{1\\}^{\lceil(n-s)/2\rceil}\\{0\\}^{n-s-\lceil(n-s)/2\rceil}$
and
$x_{4}\coloneqq\\{0\\}^{\lceil(n-s)/2\rceil}\\{1\\}^{n-s-\lceil(n-s)/2\rceil}$
as vertices of $I$, then $\mathcal{U}_{I}\cap B_{I}^{\ell}(x_{i})=\varnothing$
for all $i\in[4]$. Thus, it follows from Theorem 7.1, with $n-s$, $D$,
$\delta^{\prime}$, $1/5$, $\eta_{1}^{2^{s}}$, $\gamma/2$, $5$ and
$\mathcal{U}_{I}$ playing the roles of $n$, $D$, $\delta$,
$\varepsilon^{\prime}$, $\varepsilon$, $\gamma$, $k$ and $\mathcal{A}$,
respectively, that $\mathbb{P}_{\Omega}[\mathcal{E}_{1}]=1-o(1)$.

Step 2. Identifying scant molecules. For each $v\in V(I)$, let
$\mathcal{M}_{v}$ denote the vertex molecule of all clones of $v$ in
$\mathcal{Q}^{n}$. We say $\mathcal{M}_{v}$ is _scant_ if there exist some
layer $L$ and some vertex $x\in V(\mathcal{M}_{v}\cap L)\setminus\mathcal{U}$
such that $e_{H}(x,R_{L})<\varepsilon_{1}\delta^{\prime}n/10$, where $R_{L}$
is the clone of $R$ in $L$. Let $\mathcal{E}_{2}$ be the event that there
exists some $x\in V(I)$ such that there are at least $S^{\prime}$ vertices
$v\in B_{I}^{10\ell}(x)$ with the property that $\mathcal{M}_{v}$ is scant.
Let $\mathcal{E}_{3}$ be the event that there exist $x\in\mathcal{U}_{I}$ and
$v\in B_{I}^{5\ell}(x)$ such that $\mathcal{M}_{v}$ is scant. It follows from
Lemma 9.5 with $S^{\prime}$ and $\delta^{\prime}$ playing the roles of $C$ and
$\delta$ that $\mathbb{P}_{\Omega}[\mathcal{E}_{2}\vee\mathcal{E}_{3}]=o(1)$.
Let
$\mathcal{E}_{1}^{*}\coloneqq\mathcal{E}_{1}\wedge\overline{\mathcal{E}_{2}}\wedge\overline{\mathcal{E}_{3}}$.
Then, $\mathbb{P}_{\Omega}[\mathcal{E}_{1}^{*}]=1-o(1)$.

Condition on $\mathcal{E}_{1}^{*}$ holding. Then, there exist a set
$R\subseteq V(I)$ and a tree $T\subseteq I(G_{1})-(R\cup
B_{I}^{5}(\mathcal{U}_{I}))$ such that the following hold:

  1. $(\mathrm{T}1)$

$\Delta(T)<D$;

  2. $(\mathrm{T}2)$

for all $x\in V(I)\setminus B_{I}^{5}(\mathcal{U}_{I})$, we have that
$|N_{I}(x)\cap V(T)|\geq 4(n-s)/5$;

  3. $(\mathrm{T}3)$

for every $x\in V(I)$, we have $|\\{v\in
B_{I}^{10\ell}(x):\mathcal{M}_{v}\text{ is scant}\\}|\leq S^{\prime}$, and

  4. $(\mathrm{T}4)$

for every $x\in\mathcal{U}_{I}$ and every $v\in B_{I}^{5\ell}(x)$, we have
that $\mathcal{M}_{v}$ is not scant.

Recall this implies clones of $T$ and $R$ satisfying
$(\mathrm{T}1)$–$(\mathrm{T}4)$ exist simultaneously in each layer of $G_{1}$.

Step 3: Finding clustered robust matchings for each molecule. As in the proof
of Theorem 8.1, the aim is to find auxiliary matchings which can later be used
to pair up vertices which need to be absorbed. In the proof of Theorem 8.1, we
were able to carry out this pairing within each slice. However, we cannot
guarantee that the vertices of each special absorbing structure of Type II and
III will lie within a single slice. There will be an even number of these
vertices (zero, two or four) within each vertex molecule, but there might be
exactly one within a slice of this molecule, making it impossible to pair up
vertices within a slice. Thus we now consider the entire vertex molecule when
finding the auxiliary matching (rather than each slice separately). This would
normally make it much more difficult to link up vertices of the skeleton in
Step 18. We are able to overcome this problem by considering matchings which
are ‘clustered’, i.e. the endpoints of each matching edge either lie in a
common slice or in two consecutive slices.

Let $q\coloneqq 2^{10Dk^{*}}$ and $t\coloneqq 2^{s}/q$. For each $j\in[t]$,
let $S_{j}\coloneqq\bigcup_{i=(j-1)q+1}^{jq}L_{i}$. Given any molecule
$\mathcal{M}$, we define the slices $\mathcal{S}_{j}(\mathcal{M})\coloneqq
S_{j}\cap\mathcal{M}$. We denote by $\mathcal{S}(\mathcal{M})$ the collection
of all these slices of $\mathcal{M}$.

Let $V_{\mathrm{sc}}\subseteq V(I)$ be the set of all vertices $x\in V(I)$
such that $\mathcal{M}_{x}$ is scant. In particular, by $(\mathrm{T}4)$ we
have that $V_{\mathrm{sc}}\cap\mathcal{U}_{I}=\varnothing$. Recall
$G_{2}\sim\mathcal{Q}^{n}_{\eta_{2}}$. For each $v\in
V(I)\setminus(V_{\mathrm{sc}}\cup\mathcal{U}_{I})$, we define auxiliary
bipartite graphs $H(v)\coloneqq(V(\mathcal{M}_{v}),N_{I}(v),E_{H})$ and
$G_{2}(v)\coloneqq(V(\mathcal{M}_{v}),N_{I}(v),E_{G_{2}})$, where $E_{H}$ and
$E_{G_{2}}$ are defined as in Step 3 of the proof of Theorem 8.1 for vertices
$v\in V(I)\setminus V_{\mathrm{sc}}$ (but now the first vertex class of $H(v)$
and $G_{2}(v)$ is $V(\mathcal{M}_{v})$ rather than $V(\mathcal{S})$ for some
slice $\mathcal{S}$). For each $v\in V_{\mathrm{sc}}$, we similarly define
$H(v)$ and $G_{2}(v)$ as we did in Step 3 of the proof of Theorem 8.1, with
the same modifications as above.

For each $v\in\mathcal{U}_{I}$, we also define two such auxiliary graphs. Let
$H(v)\coloneqq(V(\mathcal{M}_{v}),N_{I}(v),E_{H}^{*})$, where $E_{H}^{*}$ is
defined as follows. Consider $v^{\prime}\in V(\mathcal{M}_{v})$ and let
$L^{v^{\prime}}$ be the layer which contains $v^{\prime}$. Let $w\in
N_{I}(v)$, and let $w_{L^{v^{\prime}}}$ be the clone of $w$ in
$L^{v^{\prime}}$. Then, if $v^{\prime}\in\mathcal{U}$, we add
$\\{v^{\prime},w\\}$ to $E_{H}^{*}$ (these can be seen as purely auxiliary
edges, and we will ignore their effect later). Otherwise,
$\\{v^{\prime},w\\}\in E_{H}^{*}$ if and only if $w\in R$ and
$\\{v^{\prime},w_{L^{v^{\prime}}}\\}\in E(H)$. In particular,
$d_{H(v)}(v^{\prime})\geq\varepsilon_{1}\delta^{\prime}n/10$ for all
$v^{\prime}\in V(\mathcal{M}_{v})$ since $\mathcal{M}_{v}$ is a not a scant
molecule. We define
$G_{2}(v)\coloneqq(V(\mathcal{M}_{v}),N_{I}(v),E_{G_{2}})$, where
$\\{v^{\prime},w\\}\in E_{G_{2}}$ if and only if
$\\{v^{\prime},w_{L^{v^{\prime}}}\\}\in E(G_{2})$.

For every $v\in V(I)$ and every slice
$\mathcal{S}\in\mathcal{S}(\mathcal{M}_{v})$, note that the partition of
$V(\mathcal{S})$ into vertices of even and odd parity is a balanced
bipartition. Define the graph
$\Gamma^{\beta}_{H(v),G_{2}(v)}(V(\mathcal{M}_{v}))$ as in Section 5.1. Thus,
$V(\Gamma^{\beta}_{H(v),G_{2}(v)}(V(\mathcal{M}_{v})))=V(\mathcal{M}_{v})$.
Furthermore, by definition,

  1. $(\mathrm{RM})$

given any $w_{1},w_{2}\in V(\mathcal{M}_{v})$, we have that
$\\{w_{1},w_{2}\\}\in E(\Gamma^{\beta}_{H(v),G_{2}(v)}(V(\mathcal{M}_{v})))$
if and only if $|N_{H(v)}(w_{1})\cap N_{G_{2}(v)}(w_{2})|\geq\beta(n-s)$ or
$|N_{G_{2}(v)}(w_{1})\cap N_{H(v)}(w_{2})|\geq\beta(n-s)$.

For each $i\in[t]$, let $\mathfrak{A}_{i}(v)$ consist of all vertices of
$V(\mathcal{S}_{i}(\mathcal{M}_{v}))$ of even parity, and let
$\mathfrak{B}_{i}(v)$ consist of those of odd parity. By applying Corollary
5.3 with $d=100D$, $\alpha=\varepsilon_{1}\delta^{\prime}/10$,
$\varepsilon=\eta_{2}$, $n=n-s$, $k=q=2^{10Dk^{*}}$, $\beta=\beta$, $t=t$,
$G=H(\mathcal{M}_{v})$ and $V(\mathcal{S}_{1}(\mathcal{M}_{v}))\cup\ldots\cup
V(\mathcal{S}_{t}(\mathcal{M}_{v}))$ as a partition of $V(\mathcal{M}_{v})$,
we obtain that, with probability at least $1-2^{-9(n-s)}\geq 1-2^{-8n}$, the
graph $\Gamma^{\beta}_{H(v),G_{2}(v)}(V(\mathcal{M}_{v}))$ is $100D$-robust-
parity-matchable with respect to
$(\bigcup_{i=1}^{t}\mathfrak{A}_{i}(v),\bigcup_{i=1}^{t}\mathfrak{B}_{i}(v))$
clustered in
$(V(\mathcal{S}_{1}(\mathcal{M}_{v})),\ldots,V(\mathcal{S}_{t}(\mathcal{M}_{v})))$.

By a union bound over all $v\in V(I)$, a.a.s.
$\Gamma^{\beta}_{H(v),G_{2}(v)}(V(\mathcal{M}_{v}))$ is $100D$-robust-parity-
matchable with respect to
$(\bigcup_{i=1}^{t}\mathfrak{A}_{i}(v),\bigcup_{i=1}^{t}\mathfrak{B}_{i}(v))$
clustered in
$(V(\mathcal{S}_{1}(\mathcal{M}_{v})),\ldots,V(\mathcal{S}_{t}(\mathcal{M}_{v})))$
for every $v\in V(I)$. We condition on this event holding and call it
$\mathcal{E}_{2}^{*}$. Thus, for each $v\in V(I)$ and each set $S\subseteq
V(\mathcal{M}_{v})$ with $|S|\leq 100D$ which contains as many odd vertices as
even vertices, there exists a perfect matching
$\mathfrak{M}(\mathcal{M}_{v},S)$ in the bipartite graph with parts consisting
of the even and odd vertices of $V(\mathcal{M}_{v})\setminus S$, respectively,
and edges given by $\Gamma^{\beta}_{H(v),G_{2}(v)}(V(\mathcal{M}_{v}))$, with
the property that, for each
$e=\\{w_{\mathrm{e}},w_{\mathrm{o}}\\}\in\mathfrak{M}(\mathcal{M}_{v},S)$, if
$w_{\mathrm{e}}\in V(\mathcal{S}_{i}(\mathcal{M}_{v}))$ for some $i\in[t]$,
then $w_{\mathrm{o}}\in V(\mathcal{S}_{i-1}(\mathcal{M}_{v}))\cup
V(\mathcal{S}_{i}(\mathcal{M}_{v}))\cup V(\mathcal{S}_{i+1}(\mathcal{M}_{v}))$
(where indices are taken cyclically). When we apply this in Step 15, we will
have $\mathcal{U}\cap V(\mathcal{M}_{v})\subseteq S$.

For each $v\in V(I)\setminus\mathcal{U}_{I}$, we denote by $\mathfrak{M}(v)$
the set of edges contained in the union (over all $S$) of the matchings
$\mathfrak{M}(\mathcal{M}_{v},S)$ (without multiplicity). For each
$v\in\mathcal{U}_{I}$, we let $u(v)$ be the unique vertex in $\mathcal{M}_{v}$
such that $u(v)\in\mathcal{U}$, and we denote by $\mathfrak{M}(v)$ the set of
edges contained in the union of the matchings
$\mathfrak{M}(\mathcal{M}_{v},S)$ over all $S$ such that $u(v)\in S$ (again,
without multiplicity). Furthermore, for each $v\in V(I)$ and each
$e=\\{w_{\mathrm{e}},w_{\mathrm{o}}\\}\in\mathfrak{M}(v)$, we let
$N(e)\coloneqq(N_{H(v)}(w_{\mathrm{e}})\cap
N_{G_{2}(v)}(w_{\mathrm{o}}))\cup(N_{G_{2}(v)}(w_{\mathrm{e}})\cap
N_{H(v)}(w_{\mathrm{o}}))$. By $(\mathrm{RM})$, we have
$|N(e)|\geq\beta(n-s)\geq\beta n/2$. Let $K\coloneqq\max_{v\in
V(I)}|\mathfrak{M}(v)|$. Thus, $K\leq\binom{2^{s}}{2}$.

Step 4: Obtaining an appropriate cube factor via the nibble. For each $x\in
V(I)$, define the sets $A_{1}(x),\ldots,A_{K}(x)$ as in Step 4 of the proof of
Theorem 8.1. Recall that $G_{3}\sim\mathcal{Q}^{n}_{\eta_{3}}$ and
$I(G_{3})\sim\mathcal{Q}^{n-s}_{\eta^{2^{s}}_{3}}$. Apply Theorem 6.6 to the
graph $I(G_{3})$, so that a.a.s. we obtain a collection $\mathcal{C}$ of
vertex-disjoint copies of $\mathcal{Q}^{\ell}$ in $I(G_{3})$ satisfying
$(\mathrm{N}1)$–$(\mathrm{N}3)$ in the proof of Theorem 8.1. Condition on the
event that such a collection $\mathcal{C}$ exists and call it
$\mathcal{E}_{3}^{*}$.

Step 5: Absorption cubes. Recall $G_{4}\sim\mathcal{Q}^{n}_{\eta_{4}}$. We
define the event $\mathcal{E}_{4}^{*}$ in the same way as in Step 5 of the
proof of Theorem 8.1. Upon conditioning on this event, for each $x\in V(I)$
and $i\in[K]$, we construct the matching $M^{\prime}(A_{i}(x))$ in exactly the
same way as well.

Consider $A_{i}(x)$, for some $x\in V(I)$ and $i\in[K]$, and let $x_{1}$,
$x_{2}$ be the clones of $x$ which correspond to $(x,i)$. For each $j\in[2]$,
let $L^{j}$ be the layer containing $x_{j}$. Similarly as in the proof of
Theorem 8.1, the following holds.

  1. $(\mathrm{AB}1)$

For each edge $(\hat{e},\hat{e}^{\prime})\in M^{\prime}(A_{i}(x))$, there is
an absorbing $\ell$-cube pair $(C^{l},C^{r})$ for $x$ in $I$ such that, for
each $j\in[2]$, the clone $(C^{l}_{j},C^{r}_{j})$ of $(C^{l},C^{r})$ in
$L^{j}$ is an absorbing $\ell$-cube pair for $x_{j}$ in $H\cup G_{2}\cup
G_{3}\cup G_{4}$. In particular, the edge joining the left absorber tip to the
third absorber vertex lies in $G_{4}$. Moreover,
$C^{l},C^{r}\in\mathcal{C}_{x}(A_{i}(x))\subseteq\mathcal{C}$ and
$(C^{l},C^{r})$ has left and right absorber tips $x+\hat{e}^{\prime}$ and
$x+\hat{e}$, respectively. Furthermore, for each $x\in V(I)\setminus
V_{\mathrm{sc}}$, these tips lie in $R$. We refer to $(C_{1}^{l},C_{1}^{r})$
and $(C_{2}^{l},C_{2}^{r})$ as the absorbing $\ell$-cube pairs for $x_{1}$ and
$x_{2}$ _associated_ with $(\hat{e},\hat{e}^{\prime})$.

Recall by the construction in Step 3 that, for each $x\in V(I)$ and $i\in[K]$,
we have $x_{1},x_{2}\notin\mathcal{U}$. In particular, this means that we do
not choose absorbing $\ell$-cube pairs for the vertices in $\mathcal{U}$ and,
thus, the auxiliary edges at the vertices in $\mathcal{U}$ introduced in the
definition of the sets $E^{*}_{H}$ in Step 3 will never be used. As discussed
before, the vertices in $\mathcal{U}$ will instead be incorporated into the
Hamilton cycle using the special absorbing structures introduced in Section
9.1.

Step 6: Removing bondless molecules. Recall
$G_{5}\sim\mathcal{Q}^{n}_{\eta_{5}}$. We define the collections
$\mathcal{C}^{\prime}$, $\mathcal{C}^{\prime\prime}$ and
$\mathcal{C}_{\mathrm{bs}}$ in the same way as in Step 6 of the proof of
Theorem 8.1, and we also define the event $\mathcal{E}^{*}_{5}$ in the same
way. We condition on this event and, as before, for each $x\in V(I)$ and each
$i\in[K]$, we modify the matching $M^{\prime}(A_{i}(x))$ into a matching
$M(A_{i}(x))$ described in $(\mathrm{AB}2)$.

Step 7: Extending the tree $\bm{T}$. For each $x\in V(I)\setminus
B^{5}_{I}(\mathcal{U}_{I})$, let $Z(x)\coloneqq N_{I}(x)\cap
V(T)\cap(\bigcup_{C\in\mathcal{C}^{\prime\prime}}V(C))$. As in the proof of
Theorem 8.1, we have that

$|Z(x)|\geq 3n/4.$ (9.4)

Recall $G_{6}\sim\mathcal{Q}^{n}_{\eta_{6}}$. We apply Theorem 7.19 in the
same way as in the proof of Theorem 8.1, but this time with $2\ell$ and
$B^{5}_{I}(\mathcal{U}_{I})$ playing the roles of $\ell$ and $W$,
respectively. Combining this with $(\mathrm{T}1)$, we conclude that a.a.s.
there exists a tree $T^{\prime}$ such that $T\subseteq
T^{\prime}\subseteq(I(G_{6})\cup T)-B^{5}_{I}(\mathcal{U}_{I})$ and the
following hold:

  1. $(\mathrm{ET}1)$

$\Delta(T^{\prime})<D+1$;

  2. $(\mathrm{ET}2)$

for all $x\in V(I)$, we have that
$|B^{2\ell}_{I}(x)\setminus(V(T^{\prime})\cup B^{5}_{I}(\mathcal{U}_{I}))|\leq
n^{3/4}$;

  3. $(\mathrm{ET}3)$

for each $x\in V(T^{\prime})\cap R$, we have that $d_{T^{\prime}}(x)=1$ and
the unique neighbour $x^{\prime}$ of $x$ in $T^{\prime}$ is such that
$x^{\prime}\in Z(x)$.

We condition on the above event holding and call it $\mathcal{E}^{*}_{6}$.

As in the proof of Theorem 8.1, for each $x\in V(I)$ and each $i\in[K]$, we
now redefine the set $M(A_{i}(x))$ so that $(\mathrm{AB}3)$ holds. It again
follows that

$|M(A_{i}(x))|\geq n/\ell^{2}-n^{3/4}\geq 4n/\ell^{3}.$ (9.5)

Step 8. Consistent systems of paths and cubes. Recall
$G_{7}\sim\mathcal{Q}^{n}_{\eta_{7}}$. For each $v\in V(I)$, let
$\mathcal{C}(v)\coloneqq\\{C\subseteq I(G_{7}):C\cong\mathcal{Q}^{\ell},v\in
V(C)\\}$. Let $\mathcal{P}\coloneqq\\{v\in V(I):|\mathcal{C}(v)|\geq\lambda
n^{\ell}\\}$. By Remark 5.13 (applied with $r=10$ and $\eta_{7}^{2^{s}}$
playing the role of $\varepsilon$), the following property holds a.a.s.

  1. $(\mathrm{D}1)$

For every $v\in V(I)$ we have $|B_{I}^{10}(v)\setminus\mathcal{P}|\leq
n^{7/8}$.

For each $v\in\mathcal{P}$, a straightforward application of Lemma 9.1 with
$\lambda$ and $\mathcal{C}(v)$ playing the roles of $\gamma$ and
$\mathcal{C}$, respectively, shows that the following holds with probability
at least $1-2^{-10n}$: there exists a subcollection
$\mathcal{C}^{\prime}(v)\subseteq\mathcal{C}(v)$, with
$|\mathcal{C}^{\prime}(v)|\geq\lambda n^{\ell}/4$, with the property that, for
every $C\in\mathcal{C}^{\prime}(v)$, the molecule $\mathcal{M}_{C}$ is bonded
in $G_{7}$. By a simple union bound over all vertices in $\mathcal{P}$, we
obtain that the following holds a.a.s.

  1. $(\mathrm{D}2)$

For every $v\in\mathcal{P}$, there exists a collection
$\mathcal{C}^{\prime}(v)\subseteq\mathcal{C}(v)$ with
$|\mathcal{C}^{\prime}(v)|\geq\lambda n^{\ell}/4$ such that, for every
$C\in\mathcal{C}^{\prime}(v)$, we have that $\mathcal{M}_{C}$ is bonded in
$G_{7}$.

Condition on the event that $(\mathrm{D}1)$ and $(\mathrm{D}2)$ hold and call
it $\mathcal{E}_{7}^{*}$.

We will show that we may extend many of the consistent systems of paths given
by $(\mathrm{R}4)$ into special absorbing structures. Recall that, since $H$
is $(s,\ell,\varepsilon_{1},\varepsilon_{2},\gamma,\mathcal{U})$-robust, for
every $x\in\mathcal{U}$ and each pair of directions
$a,b\in\mathcal{D}(\mathcal{Q}^{n})$, there exists a collection
$\mathfrak{C}(x,a,b)$ of $(x,a,b)$-consistent systems of paths in
$H\cup\\{\\{x,x+a\\}\\{x,x+b\\}\\}$ satisfying $(\mathrm{R}4)$. By
$(\mathrm{D}1)$, for every $x\in\mathcal{U}$ and
$a,b\in\mathcal{D}(\mathcal{Q}^{n})$

  1. (CS)

there exists a subcollection
$\mathfrak{C}^{\prime}(x,a,b)\subseteq\mathfrak{C}(x,a,b)$ which satisfies
$(\mathrm{R}4)$ with $\gamma/2$ playing the role of $\gamma$ and such that,
for every $\mathit{CS}\in\mathfrak{C}^{\prime}(x,a,b)$, we have
$\mathrm{endmol}(\mathit{CS})\subseteq\mathcal{P}$.

Let $L$ be any layer of $\mathcal{Q}^{n}$. For each $x\in\mathcal{U}$, let
$\mathrm{End}(x)\coloneqq\bigcup_{a,b\in\mathcal{D}(\mathcal{Q}^{n})}\bigcup_{\mathit{CS}\in\mathfrak{C}^{\prime}(x,a,b)}\mathrm{endmol}(\mathit{CS})$,
let
$\mathrm{End\,II}(x)\coloneqq\bigcup_{a,b\in\mathcal{D}(\mathcal{Q}^{n})\setminus\mathcal{D}(L)}\bigcup_{\mathit{CS}\in\mathfrak{C}^{\prime}(x,a,b)}\mathrm{endmol}(\mathit{CS})$,
and let $x_{I}\in V(I)$ be such that $x$ is a clone of $x_{I}$. Given any tree
$T^{\bullet}\subseteq I$ and any cube $C\subseteq V(I)$, we say that $C$
_meets $T^{\bullet}$_ if $V(C)\cap V(T^{\bullet})\neq\varnothing$. Recall
that, for any $y,z\in V(I)$, we denote the set of directions in a shortest
path in $I$ between $y$ and $z$ by $\mathcal{D}(y,z)$.

######  Claim 9.1.

For each $x\in\mathcal{U}$ and each $z\in\mathrm{End}(x)$, there exists a
collection of cubes
$\mathcal{C}^{\prime\prime}(z)\subseteq\mathcal{C}^{\prime}(z)$ with
$|\mathcal{C}^{\prime\prime}(z)|=20\ell$ which satisfies the following
properties.

  1. $(\mathrm{i})$

Every $C\in\mathcal{C}^{\prime\prime}(z)$ meets $T^{\prime}$.

  2. $(\mathrm{ii})$

For every $C\in\mathcal{C}^{\prime\prime}(z)$, we have
$\mathcal{D}(C)\cap\mathcal{D}(x_{I},z)=\varnothing$.

  3. $(\mathrm{iii})$

For every $C_{1},C_{2}\in\mathcal{C}^{\prime\prime}(z)$, we have $V(C_{1})\cap
V(C_{2})=\\{z\\}$.

  4. $(\mathrm{iv})$

For each $x\in\mathcal{U}$, let
$\bm{\mathcal{C}^{\prime\prime}}(x)\coloneqq\bigcup_{z\in\mathrm{End\,II}(x)}\mathcal{C}^{\prime\prime}(z)$.
For each $d\in\mathcal{D}(L)$ and each $x\in\mathcal{U}$, let
$\alpha(d,x)\coloneqq|\\{C\in\bm{\mathcal{C}^{\prime\prime}}(x):d\in\mathcal{D}(C)\\}|$.
For all $d\in\mathcal{D}(L)$ and $x\in\mathcal{U}$, we have that
$\alpha(d,x)\leq n/\ell^{3}$.

###### Proof.

Fix any vertex $x\in\mathcal{U}$. Let $\mathfrak{m}\coloneqq|\mathrm{End}(x)|$
and $m\coloneqq|\mathrm{End\,II}(x)|$, and consider an arbitrary labelling
$z_{1},\ldots,z_{m},z_{m+1},\ldots,z_{\mathfrak{m}}$ of the vertices in
$\mathrm{End}(x)$ such that all vertices in $\mathrm{End\,II}(x)$ come first.
Observe that, by the definition of Type II consistent systems of paths (see
Section 9.1), we have that $m\leq n$. We will now iteratively define the sets
$\mathcal{C}^{\prime\prime}(z_{i})$ for each $i\in[\mathfrak{m}]$.

Fix first any $i\in[m]$, and suppose that a set
$\mathcal{C}^{\prime\prime}(z_{j})$ satisfying the claim is already defined
for all $j\in[i-1]$. Let
$\bm{\mathcal{C}^{\prime\prime}}(x,i)\coloneqq\bigcup_{j=1}^{i-1}\mathcal{C}^{\prime\prime}(z_{j})$.
For each $d\in\mathcal{D}(L)$, let
$\alpha(d,x,i)\coloneqq|\\{C\in\bm{\mathcal{C}^{\prime\prime}}(x,i):d\in\mathcal{D}(C)\\}|$.
Let $\mathcal{D}^{*}\coloneqq\\{d\in\mathcal{D}(L):\alpha(d,x,i)\geq
n/\ell^{3}\\}$. Observe that $|\mathcal{D}^{*}|\leq 20\ell^{5}$. Let
$\mathcal{C}^{\prime\prime\prime}(z_{i})$ be the set of all cubes
$C\in\mathcal{C}^{\prime}(z_{i})$ such that $C$ meets $T^{\prime}$ and
$\mathcal{D}(C)\cap(\mathcal{D}(x_{I},z_{i})\cup\mathcal{D}^{*})=\varnothing$
(i.e., they satisfy $(\mathrm{i})$ and $(\mathrm{ii})$ and, if added to the
collection, would not violate $(\mathrm{iv})$). We claim that
$|\mathcal{C}^{\prime\prime\prime}(z_{i})|\geq\lambda n^{\ell}/5$. Indeed,
observe that ${\rm dist}(x_{I},z_{i})\leq 2$ and, thus, the number of cubes
$C\in\mathcal{C}^{\prime}(z_{i})$ such that
$\mathcal{D}(C)\cap(\mathcal{D}(x_{I},z_{i})\cup\mathcal{D}^{*})\neq\varnothing$
is at most $(20\ell^{5}+2)n^{\ell-1}$, and, by $(\mathrm{ET}2)$ and
$(\mathrm{R}3)$, the number of such cubes which do not meet $T^{\prime}$ is at
most $n^{\ell-2}$. The bound then follows by $(\mathrm{D}2)$.

We can now construct $\mathcal{C}^{\prime\prime}(z_{i})$ by obtaining cubes
$C_{1}(z_{i}),\ldots,C_{20\ell}(z_{i})$ iteratively. Note that, for any pair
of cubes $C_{1},C_{2}\in\mathcal{C}^{\prime}(z_{i})$, we have that $z\in
V(C_{1})\cap V(C_{2})$. Then, $(\mathrm{iii})$ is equivalent to having that
$\mathcal{D}(C_{1})\cap\mathcal{D}(C_{2})=\varnothing$. For each
$k\in[20\ell]$, we proceed as follows. Let
$\mathcal{D}^{\prime}_{k}\coloneqq\bigcup_{j=1}^{k-1}\mathcal{D}(C_{j}(z_{i}))$.
Note that $|\mathcal{D}^{\prime}_{k}|\leq 20\ell^{2}\leq\lambda n/8$. Now,
applying Remark 9.2 with $n-s$, $z$, $\lambda/5$, $\lambda/8$ and
$\mathcal{D}^{\prime}_{k}$ playing the roles of $n$, $x$, $\eta$,
$\eta^{\prime}$ and $\mathcal{D}^{\prime}$, respectively, we deduce that there
is a cube $C_{k}(z_{i})\in\mathcal{C}^{\prime\prime\prime}(z_{i})$ with
$\mathcal{D}(C_{k}(z_{i}))\cap\mathcal{D}^{\prime}_{k}=\varnothing$. By
enforcing that $(\mathrm{iii})$ holds, it follows that each direction is used
at most once in the cubes that were added in this step. It then follows that
$(\mathrm{iv})$ holds as well.

Consider now any $i\in[\mathfrak{m}]\setminus[m]$, and suppose that a set
$\mathcal{C}^{\prime\prime}(z_{j})$ satisfying the claim is already defined
for all $j\in[i-1]$. Let $\mathcal{C}^{\prime\prime\prime}(z_{i})$ be the set
of all cubes $C\in\mathcal{C}^{\prime}(z_{i})$ such that $C$ meets
$T^{\prime}$ and $\mathcal{D}(C)\cap\mathcal{D}(x_{I},z_{i})=\varnothing$
(i.e., they satisfy $(\mathrm{i})$ and $(\mathrm{ii})$). As above, we claim
that $|\mathcal{C}^{\prime\prime\prime}(z_{i})|\geq\lambda n^{\ell}/5$.
Indeed, the number of cubes $C\in\mathcal{C}^{\prime}(z_{i})$ such that
$\mathcal{D}(C)\cap\mathcal{D}(x_{I},z_{i})\neq\varnothing$ is at most
$2n^{\ell-1}$, and, again, the number of such cubes which do not meet
$T^{\prime}$ is at most $n^{\ell-2}$. The bound then follows by
$(\mathrm{D}2)$.

We can now construct $\mathcal{C}^{\prime\prime}(z_{i})$ as above. For each
$k\in[20\ell]$, we proceed as follows. Let
$\mathcal{D}^{\prime}_{k}\coloneqq\bigcup_{j=1}^{k-1}\mathcal{D}(C_{j}(z_{i}))$.
Note that $|\mathcal{D}^{\prime}_{k}|\leq 20\ell^{2}\leq\lambda n/8$. Now,
applying Remark 9.2 with $n-s$, $z$, $\lambda/5$, $\lambda/8$ and
$\mathcal{D}^{\prime}_{k}$ playing the roles of $n$, $x$, $\eta$,
$\eta^{\prime}$ and $\mathcal{D}^{\prime}$, respectively, we deduce that there
is a cube $C_{k}(z_{i})\in\mathcal{C}^{\prime\prime\prime}(z_{i})$ with
$\mathcal{D}(C_{k}(z_{i}))\cap\mathcal{D}^{\prime}_{k}=\varnothing$. ∎

Let
$J^{1}\coloneqq\bigcup_{x\in\mathcal{U}}\bigcup_{z\in\mathrm{End}(x)}\bigcup_{C\in\mathcal{C}^{\prime\prime}(z)}\mathcal{M}_{C}$,
where $\mathcal{C}^{\prime\prime}(z)$ are the sets given by 9.1, and let
$G^{*}_{7}\subseteq G_{7}$ consist of all edges of $G_{7}$ which have
endpoints in different layers.

######  Claim 9.2.

$J^{1}\cup G^{*}_{7}$ is $(\mathcal{U},\ell^{3},s)$-good and $\Delta(J^{1}\cup
G^{*}_{7})\leq 50\ell^{4}$.

###### Proof.

In order to see that $J^{1}\cup G^{*}_{7}$ is $(\mathcal{U},\ell^{3},s)$-good,
observe first that the edges of $G^{*}_{7}$ do not affect this definition, so
it suffices to see that $J^{1}$ is $(\mathcal{U},\ell^{3},s)$-good. By
9.1$(\mathrm{ii})$, for all $x\in\mathcal{U}$, $z\in\mathrm{End}(x)$ and
$C\in\mathcal{C}^{\prime\prime}(z)$ we have that ${\rm dist}(x_{I},C)={\rm
dist}(x_{I},z)$. In particular, by the definition of the different consistent
systems of paths (see Section 9.1), it follows that the only cubes which
affect whether $J^{1}$ is $(\mathcal{U},\ell^{3},s)$-good or not are those of
the collection $\bm{\mathcal{C}^{\prime\prime}}(x)$ described in
9.1$(\mathrm{iv})$. But then, by 9.1$(\mathrm{iv})$, we have that no direction
$d\in\mathcal{D}(L)$ is used more than $n/\ell^{3}$ times, as required.

Note that $\Delta(G_{7}^{*})\leq s=10\ell$, by construction. We will now show
that $\Delta(J^{1})\leq 45\ell^{4}$. Observe that $J^{1}$ does not contain any
edges with endpoints in different layers. In particular, $J^{1}$ consists of
clones of the same subgraph of $I$, that is
$I(J^{1})=\bigcup_{x\in\mathcal{U}}\bigcup_{z\in\mathrm{End}(x)}\bigcup_{C\in\mathcal{C}^{\prime\prime}(z)}C$.
By this observation, it is enough to show that $\Delta(I(J^{1}))\leq
45\ell^{4}$.

Recall that, by $(\mathrm{R}3)$, given any distinct $x,y\in\mathcal{U}_{I}$,
we have that ${\rm dist}(x,y)\geq\gamma n/2$. In particular, by this
observation and 9.1$(\mathrm{ii})$, it follows that, for all
$x\in\mathcal{U}_{I}$, we have $d_{I(J^{1})}(x)=0$. We also note that, for
every $z\in V(I)$ for which ${\rm dist}(z,\mathcal{U}_{I})\geq\ell+3$, we have
$d_{I(J^{1})}(z)=0$. Now, fix any $x\in\mathcal{U}_{I}$ and $z\in V(I)$ such
that ${\rm dist}(z,x)=t$, for some $t\in[\ell+2]$. We claim that
$d_{I(J^{1})}(z)\leq 2t^{2}\cdot 20\ell^{2}\leq 45\ell^{4}$.

Suppose first that $t=1$. Then, by 9.1$(\mathrm{ii})$, for every edge $e\in
E(I(J^{1}))$ incident with $z$, we have $e\in E(C)$ for some
$C\in\mathcal{C}^{\prime\prime}(z)$, and hence
$d_{I(J^{1})}(z)\leq\ell|\mathcal{C}^{\prime\prime}(z)|=20\ell^{2}$, as we
wanted to show. Suppose now that $t\geq 2$ and let
$\mathcal{D}(z,x)=\\{d_{1},\ldots,d_{t}\\}$. Every edge $e$ incident with $z$
must come from the edges of a cube $C\in\mathcal{C}^{\prime\prime}(w)$, for
some $w\in\mathrm{End}(x)$. Moreover, by 9.1$(\mathrm{ii})$, we must have
$\mathcal{D}(x,w)\subseteq\mathcal{D}(x,z)$. As there are at most $t+t^{2}\leq
2t^{2}$ vertices $w\in V(I)$ such that
$\mathcal{D}(x,w)\subseteq\mathcal{D}(x,z)$ and ${\rm dist}(x,w)\in[2]$, we
have have that $d_{I(J^{1})}(z)\leq 2t^{2}20\ell^{2}$, which concludes the
proof of the claim. ∎

Step 9: Fixing a collection of absorbing $\bm{\ell}$-cube pairs for the
vertices in scant molecules. In this step, we use
$G_{8}\sim\mathcal{Q}^{n}_{\eta_{8}}$ to alter $T^{\prime}$ so that any tips
of absorbing $\ell$-cube pairs for vertices $x\in V_{\mathrm{sc}}$ which do
not lie in $R$ are relocated from the tree $T^{\prime}$ to the reservoir. We
follow the same approach as in Step 8 of the proof of Theorem 8.1. In
particular, we define an event $\mathcal{E}_{8}^{*}$ (which is analogous to
$\mathcal{E}_{7}^{*}$ in the proof of Theorem 8.1) and condition that it
holds. This then gives a set of absorbing $\ell$-cube pairs
$\mathcal{C}^{\mathrm{sc}}_{1}=\\{(C^{l}(x,j,k),C^{r}(x,j,k))\subseteq I:x\in
V_{\mathrm{sc}},j\in[K],k\in[2^{s+1}\Psi]\\}$, where each
$(C^{l}(x,j,k),C^{r}(x,j,k))$ is an absorbing $\ell$-cube pair for $x$, which
satisfies that

  1. $(\mathrm{CD})$

for all distinct $(x,j,k),(x^{\prime},j^{\prime},k^{\prime})\in
V_{\mathrm{sc}}\times[K]\times[2^{s+1}\Psi]$, $C^{l}(x,j,k)$ and
$C^{r}(x,j,k)$ are both vertex-disjoint from
$C^{l}(x^{\prime},j^{\prime},k^{\prime})$ and
$C^{r}(x^{\prime},j^{\prime},k^{\prime})$.

We define $P^{\prime}$ and $P$ as in Step 8 of the proof of Theorem 8.1.
Observe that $(\mathrm{T}4)$ implies that $(P^{\prime}\cup V(P))\cap
B^{2\ell}(\mathcal{U}_{I})=\varnothing$. Let $T^{\textsc{iv}}\coloneqq
T^{\prime}[V(T^{\prime})\setminus P^{\prime}]\cup P$, which is connected, and
let $T^{\prime\prime}$ be a spanning tree of $T^{\textsc{iv}}$. In particular,
it follows from the above and the definitions of $T$ and $T^{\prime}$ in Steps
1 and 7 that

$T^{\prime\prime}\subseteq I(G_{1}\cup G_{6}\cup
G_{8})-B_{I}^{5}(\mathcal{U}_{I})\subseteq I-B_{I}^{5}(\mathcal{U}_{I}).$
(9.6)

Furthermore, as in Step 8 of the proof of Theorem 8.1, we have that

$\Delta(T^{\prime\prime})\leq 12D.$ (9.7)

Define the (new) reservoir $R^{\prime}\coloneqq(R\cup P^{\prime})\setminus
V(P)$.

For each $x\in V(I)\setminus B^{5}_{I}(\mathcal{U}_{I})$, let
$Z^{\prime}(x)\coloneqq Z(x)\cap V(T^{\prime\prime})$ (where $Z(x)$ is as
defined in Step 7). It follows by (9.4) and $(\mathrm{T}3)$ that

$|Z^{\prime}(x)|\geq 3n/4-4\cdot 2^{s}\Psi KS^{\prime}\geq n/2.$

Choose any vertex $x\in V(I)$ with ${\rm dist}(x,\mathcal{U}_{I})\geq 3\ell$.
Again by $(\mathrm{T}3)$, there are at most $4\cdot 2^{s+\ell}\Psi
KS^{\prime}$ vertices in $Z^{\prime}(x)$ which lie in cubes of absorbing
$\ell$-cube pairs of $\mathcal{C}^{\mathrm{sc}}_{1}$. Choose any vertex $y\in
Z^{\prime}(x)$ which does not lie in any of those cubes. Denote the cube
$C\in\mathcal{C}^{\prime\prime}$ which contains $y$ by $C^{\bullet}$.

For each $x\in V(I)\setminus V_{\mathrm{sc}}$ and each $i\in[K]$, we now
redefine the set $M(A_{i}(x))$ as follows.

  1. $(\mathrm{AB}4)$

Let $M(A_{i}(x))$ retain only those edges whose associated absorbing
$\ell$-cube pair $(C^{l},C^{r})$ satisfies that both $C^{l}$ and $C^{r}$ are
different from $C^{\bullet}$ and vertex-disjoint from both cubes of all
absorbing $\ell$-cube pairs of $\mathcal{C}^{\mathrm{sc}}_{1}$, and both tips
$x^{l}$ and $x^{r}$ satisfy that $x^{l},x^{r}\in R\setminus V(P)\subseteq
R^{\prime}$.

Note that, by $(\mathrm{T}3)$, we have $|B^{\ell+1}_{I}(x)\cap V(P)|\leq
21\cdot 2^{s}\Psi DKS^{\prime}$ and $|B^{\ell+1}_{I}(x)\cap
V(\bigcup_{(C^{l},C^{r})\in\mathcal{C}^{\mathrm{sc}}_{1}}(C^{l}\cup
C^{r}))|\leq 4\cdot 2^{\ell+s}\Psi KS^{\prime}$. Combining this with (9.5) and
$(\mathrm{AB}1)$, it follows that

$|M(A_{i}(x))|\geq 4n/\ell^{3}-(21D+4\cdot 2^{\ell})2^{s}\Psi
KS^{\prime}-1\geq 2n/\ell^{3}.$ (9.8)

Step 10: Fixing a collection of absorbing $\bm{\ell}$-cube pairs for vertices
in non-scant molecules and vertices near $\bm{\mathcal{U}}$. At this point, it
is not yet clear which vertices will need to eventually be absorbed into the
long cycle we construct. For vertices in $I$ which are ‘far’ from
$\mathcal{U}_{I}$, we can already determine those which will have clones that
will need to be absorbed (though we cannot yet determine the precise clones).
However, for vertices which are ‘near’ $\mathcal{U}_{I}$, we still cannot say
which of them will have clones that need to be absorbed (this depends on the
special absorbing structure which is fixed once the edges of $H^{\prime}$ are
revealed). As a result, we proceed as if all of the clones of vertices in $I$
near $\mathcal{U}_{I}$ will need to be absorbed. Recall that
$\mathcal{C}^{\prime}$ and $\mathcal{C}^{\prime\prime}$ were introduced in
Step 6. Let

$\mathcal{C}^{\prime\prime\prime}\coloneqq\\{C\in\mathcal{C}^{\prime}:V(C)\cap
V(T^{\prime\prime})\neq\varnothing\\}\quad\text{ and }\quad
V_{\mathrm{abs}}^{\prime}\coloneqq(V(I)\setminus\bigcup_{C\in\mathcal{C}^{\prime\prime\prime}}V(C))\cup
B_{I}^{3\ell}(\mathcal{U}_{I}).$

We will now fix a collection of absorbing $\ell$-cube pairs for all vertices
in each vertex molecule $\mathcal{M}_{x}$ with $x\in
V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$, except for the vertices
of $\mathcal{U}$.

Similarly as in (8.12), we have

$|B^{2\ell}_{I}(x)\setminus(V(T^{\prime\prime})\cup
B_{I}^{5}(\mathcal{U}_{I}))|\leq 2n^{3/4}.$ (9.9)

For all $x\in\bigcup_{C\in\mathcal{C}^{\prime\prime}}V(C)$, by combining
$(\mathrm{N}1)$, (9.9) and $(\mathrm{R}3)$ with the definition of bondlessly
surrounded molecules, we have that

$|\mathcal{C}_{x}\cap\mathcal{C}^{\prime\prime\prime}|\geq(1-2^{-\ell-5s+1})n,$
(9.10)

where $\mathcal{C}_{x}$ is the collection of all those $C\in\mathcal{C}$ such
that $x\notin V(C)$ and $N_{I}(x)\cap V(C)\neq\varnothing$.

Recall that, for any $x\in V(I)$, each index $i\in[K]$ is given by a unique
edge $e\in\mathfrak{M}(x)$ via the relation $N(e)=A_{i}(x)$. Recall also the
definition of $\mathfrak{M}(x)$ from Step 3. We now prove the following claim,
which is similar to 8.2 (apart from the new property $(\mathrm{ii})$).

######  Claim 9.3.

For each $x\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ and each
$e\in\mathfrak{M}(x)$, there exists a set $\mathcal{C}_{1}^{\mathrm{abs}}(e)$
of $2^{s+1}\Psi$ absorbing $\ell$-cube pairs
$(C_{k}^{l}(e),C_{k}^{r}(e))\subseteq I$, one for each $k\in[2^{s+1}\Psi]$,
which satisfies the following:

  1. $(\mathrm{i})$

for all $x\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$,
$e\in\mathfrak{M}(x)$ and $k\in[2^{s+1}\Psi]$, the absorbing $\ell$-cube pair
$(C_{k}^{l}(e),C_{k}^{r}(e))$ is associated with some edge in $M(A_{j}(x))$,
for some $j\in[K]$;

  2. $(\mathrm{ii})$

for all $x\in B_{I}^{3\ell}(\mathcal{U}_{I})$, $e\in\mathfrak{M}(x)$ and
$k\in[2^{s+1}\Psi]$, the absorbing $\ell$-cube pair
$(C_{k}^{l}(e),C_{k}^{r}(e))$ has tips $x_{k}^{l}(e)$ and $x_{k}^{r}(e)$ which
satisfy that ${\rm dist}(x,\mathcal{U}_{I})<{\rm
dist}(x_{k}^{l}(e),\mathcal{U}_{I})$ and ${\rm dist}(x,\mathcal{U}_{I})<{\rm
dist}(x_{k}^{r}(e),\mathcal{U}_{I})$, and

  3. $(\mathrm{iii})$

for all $x,x^{\prime}\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$,
all $e\in\mathfrak{M}(x)$ and $e^{\prime}\in\mathfrak{M}(x^{\prime})$, and all
$k,k^{\prime}\in[2^{s+1}\Psi]$ with
$(x,e,k)\neq(x^{\prime},e^{\prime},k^{\prime})$, the absorbing $\ell$-cube
pairs $(C_{k}^{l}(e),C_{k}^{r}(e))$ and
$(C_{k^{\prime}}^{l}(e^{\prime}),C_{k^{\prime}}^{r}(e^{\prime}))$ satisfy that
$(V(C_{k}^{l}(e))\cup
V(C_{k}^{r}(e)))\cap(V(C_{k^{\prime}}^{l}(e^{\prime}))\cup
V(C_{k^{\prime}}^{r}(e^{\prime})))=\varnothing$.

###### Proof.

Let $\mathcal{V}\coloneqq\bigcup_{x\in V_{\mathrm{abs}}^{\prime}\setminus
V_{\mathrm{sc}}}\mathfrak{M}(x)$. Let $K^{\prime}\coloneqq|\mathcal{V}|$, and
let $f_{1},\dots,f_{K^{\prime}}$ be an ordering of the edges in $\mathcal{V}$.
Given any $i\in[K^{\prime}]$, the edge $f_{i}$ corresponds to a pair
$(x,j(i))$, where $x\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$
and $j(i)\in[K]$. If $x\notin B_{I}^{3\ell}(\mathcal{U}_{I})$, let
$\mathfrak{C}_{i}$ be the collection of absorbing $\ell$-cube pairs for $x$ in
$I$ associated with some edge of $M(A_{j(i)}(x))$. Otherwise, let
$\mathfrak{C}_{i}$ be the same collection, after removing all those absorbing
$\ell$-cube pairs for which $(\mathrm{ii})$ does not hold. Since each $x\in
B_{I}^{3\ell}(\mathcal{U}_{I})$ has at most $3\ell$ neighbours $y\in N_{I}(x)$
such that ${\rm dist}(x,\mathcal{U}_{I})\geq{\rm dist}(y,\mathcal{U}_{I})$, it
follows by (9.8) that $|\mathfrak{C}_{i}|\geq n/\ell^{3}$ for all
$i\in[K^{\prime}]$. In particular, by $(\mathrm{AB}2)$, each of the absorbing
$\ell$-cube pairs $(C^{l},C^{r})$ in any of the collections $\mathfrak{C}_{i}$
satisfies that $C^{l},C^{r}\in\mathcal{C}^{\prime\prime}$.

Let $\mathcal{H}$ be the $2^{s+1}\Psi K^{\prime}$-edge-coloured auxiliary
multigraph with $V(\mathcal{H})\coloneqq\mathcal{C}^{\prime\prime}$, which
contains one edge of colour $(i,k)\in[K^{\prime}]\times[2^{s+1}\Psi]$ between
$C$ and $C^{\prime}$ whenever $(C,C^{\prime})\in\mathfrak{C}_{i}$ or
$(C^{\prime},C)\in\mathfrak{C}_{i}$. In particular, $\mathcal{H}$ contains at
least $n/\ell^{3}$ edges of each colour. We now bound $\Delta(\mathcal{H})$.
Consider any $C\in V(\mathcal{H})$. Note that, for each edge $e$ of
$\mathcal{H}$ incident to $C$, there exists some $x=x(e)\in
V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ such that $C$ together
with some other cube $C^{\prime}\in V(\mathcal{H})$ forms an absorbing
$\ell$-cube pair for $x$. In particular, $x$ must be adjacent to $C$ in $I$.
Let $\overline{\partial}(C)\coloneqq\\{x(e):e\in E(\mathcal{H})\text{ is
incident to }C\\}$. Moreover, if $e$ has colour $(i,z)$, then
$f_{i}\in\mathfrak{M}(x)$ (and $f_{i}$ has corresponding pair $(x,j(i))$ for
some $j(i)\in[K]$). Since $f_{i}\in\mathfrak{M}(x)$ and
$|\mathfrak{M}(x)|\leq\binom{2^{s}}{2}$, it follows that each vertex $y$ which
is adjacent to $C$ in $I$ can play the role of $x$ for at most
$2^{s+1}\Psi\cdot 2^{2s}$ edges of $\mathcal{H}$ incident to $C$. Thus,
$d_{\mathcal{H}}(C)\leq 2^{3s+1}\Psi|\overline{\partial}(C)|$.

Fix a cube $C\in V(\mathcal{H})$. In order to bound
$|\overline{\partial}(C)|$, consider first $|\overline{\partial}(C)\cap
B_{I}^{3\ell}(\mathcal{U}_{I})|$. Recall that, by $(\mathrm{R}3)$, there is at
most one vertex $z\in\mathcal{U}_{I}\cap B_{I}^{3\ell}(V(C))$. Furthermore,
since the property described in $(\mathrm{ii})$ holds for all absorbing
$\ell$-cube pairs for vertices in $B_{I}^{3\ell}(\mathcal{U}_{I})$ represented
in $\mathcal{H}$, it follows that each vertex $x\in V(C)$ has at most
$3\ell+1$ neighbours in
$B_{I}^{3\ell}(\mathcal{U}_{I})\cap\overline{\partial}(C)$. Thus, in total,
$|\overline{\partial}(C)\cap
B_{I}^{3\ell}(\mathcal{U}_{I})|\leq(3\ell+1)2^{\ell}$. Consider now
$|\overline{\partial}(C)\setminus B_{I}^{3\ell}(\mathcal{U}_{I})|$. Note that
$\overline{\partial}(C)\setminus
B_{I}^{3\ell}(\mathcal{U}_{I})\subseteq(V_{\mathrm{abs}}^{\prime}\cap
N_{I}(V(C)))\setminus B_{I}^{3\ell}(\mathcal{U}_{I})\subseteq
N_{I}(V(C))\setminus\bigcup_{C^{\prime}\in\mathcal{C}^{\prime\prime\prime}}V(C^{\prime})$.
By (9.10), the number of vertices in $V_{\mathrm{abs}}^{\prime}\setminus
B_{I}^{3\ell}(\mathcal{U}_{I})$ which are adjacent to $C$ is at most
$2|C|n/{2^{\ell+5s}}$, that is, $|\overline{\partial}(C)\setminus
B_{I}^{3\ell}(\mathcal{U}_{I})|\leq 2n/2^{5s}$. We conclude that
$|\overline{\partial}(C)|\leq 3n/2^{5s}$ and, thus, $d_{\mathcal{H}}(C)\leq
2^{3s+1}\Psi 3n/{2^{5s}}\leq n/\ell^{4}$.

Since each colour class has size at least $n/\ell^{3}$ and
$\Delta(\mathcal{H})\leq n/\ell^{4}$, by Lemma 5.5, $\mathcal{H}$ contains a
rainbow matching of size $2^{s+1}\Psi K^{\prime}$. For each
$(i,z)\in[K^{\prime}]\times[2^{s+1}\Psi]$, let
$(C_{z}^{l}(f_{i}),C_{z}^{r}(f_{i}))\in\mathfrak{C}_{i}$ be the absorbing
$\ell$-cube pair of colour $(i,z)$ in this rainbow matching. This ensures that
$(\mathrm{iii})$ holds, while $(\mathrm{i})$ and $(\mathrm{ii})$ follow by
construction. ∎

For each $x\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ and each
$i\in[K]$, let
$\mathcal{C}^{\mathrm{abs}}_{1}(x,i)\coloneqq\mathcal{C}^{\mathrm{abs}}_{1}(e)$
be the set of absorbing $\ell$-cube pairs guaranteed by 9.3, where
$e\in\mathfrak{M}(x)$ is the unique edge such that $A_{i}(x)=N(e)$. Similarly,
for each $k\in[2^{s+1}\Psi]$, let
$(C^{l}(x,i,k),C^{r}(x,i,k))\coloneqq(C_{k}^{l}(e),C_{k}^{r}(e))$. Let
$\mathcal{C}^{\mathrm{abs}}_{1}\coloneqq\bigcup_{x\in
V_{\mathrm{abs}}^{\prime}\setminus
V_{\mathrm{sc}}}\bigcup_{i\in[K]}\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$.

Let $G\coloneqq\bigcup_{i=1}^{8}G_{i}$. Recall that $G^{*}_{7}$ and $J^{1}$
were defined in Step 8. We let $Q^{\prime}\subseteq G$ be the spanning
subgraph with edge set

$E(Q^{\prime})\coloneqq E(J^{1})\cup E(G_{4}^{*})\cup E(G_{5}^{*})\cup
E(G_{7}^{*})\cup\bigcup_{C\in\mathcal{C}^{\prime}}E(\mathcal{M}_{C})\cup\bigcup_{i=1}^{2^{s}}E(T^{\prime\prime}_{L_{i}}),$

where $G_{4}^{*}$ and $G_{5}^{*}$ are as defined in Step 9 of the proof of
Theorem 8.1 (but with $V_{\mathrm{abs}}^{\prime}$ playing the role of
$V_{\mathrm{abs}}$). Note that, using 9.2 and (9.7), we have that
$\Delta(Q^{\prime})\leq\Phi$.

######  Claim 9.4.

$Q^{\prime}$ is $(\mathcal{U},2\ell^{2},s)$-good.

###### Proof.

Indeed, observe that this fact only depends on those edges contained within a
layer which are incident to a neighbour of $x$ in $\mathcal{Q}^{n}$, for some
$x\in\mathcal{U}$. Therefore, the graph $G^{*}_{5}$ has no effect here. By
property $(\mathrm{C}3)$ below, the graph
$\bigcup_{i=1}^{2^{s}}T^{\prime\prime}_{L_{i}}$ also has no effect. Now, by
9.2 we have that $J^{1}\cup G_{7}^{*}$ is $(\mathcal{U},\ell^{3},s)$-good, and
$\bigcup_{C\in\mathcal{C}^{\prime}}\mathcal{M}_{C}$ is
$(\mathcal{U},\ell^{3},s)$-good by $(\mathrm{N}2)$ combined with
$(\mathrm{R}3)$. Finally, consider $G^{*}_{4}$. For each $x\in
V_{\mathrm{abs}}^{\prime}\cup V_{\mathrm{sc}}$, $i\in[K]$ and
$k\in[2^{s+1}\Psi]$, let $e(x,i,k)$ be the edge between the left absorber tip
and the third absorber vertex of
$(C^{l}(x,i,k),C^{r}(x,i,k))\in\mathcal{C}^{\mathrm{sc}}_{1}\cup\mathcal{C}^{\mathrm{abs}}_{1}$.
Observe that, for all $x\in V_{\mathrm{abs}}^{\prime}\cup V_{\mathrm{sc}}$
such that ${\rm dist}(x,\mathcal{U}_{I})\geq 5$, all $i\in[K]$ and all
$k\in[2^{s+1}\Psi]$, we have that $e(x,i,k)$ does not affect whether
$Q^{\prime}$ is $(\mathcal{U},2\ell^{2},s)$-good or not. In particular, by
$(\mathrm{T}4)$, this is true for all $x\in V_{\mathrm{sc}}$. Now consider
each $x\in V_{\mathrm{abs}}^{\prime}$ such that ${\rm
dist}(x,\mathcal{U}_{I})<5$. By 9.3$(\mathrm{ii})$, it follows that $e(x,i,k)$
only affects our claim when $x\in\mathcal{U}_{I}$. Observe that, for each
$i\in[K]$ and $k\in[2^{s+1}\Psi]$, the direction of $e(x,i,k)$ is the same as
that of the edge $e^{\prime}(x,i,k)$ joining $x$ to the right absorber tip of
$(C^{l}(x,i,k),C^{r}(x,i,k))$. By 9.3$(\mathrm{iii})$, all cubes of absorbing
$\ell$-cube pairs in $\bigcup_{i\in[K]}\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$
are vertex disjoint, which implies that each edge $e^{\prime}(x,i,k)$ with
$i\in[K]$ and $k\in[2^{s+1}\Psi]$ uses a different direction. Hence,
$G^{*}_{4}$ is $(\mathcal{U},n,s)$-good, and the claim follows. ∎

Note that $T^{\prime\prime}\subseteq I(Q^{\prime})$, $R^{\prime}\subseteq
V(I)$, and $C\subseteq I(Q^{\prime})$ for all $C\in\mathcal{C}^{\prime}$.
Recall the definitions of $C^{\prime\prime}$ from Step 6 and
$C^{\prime\prime\prime}$ from Step 10. For any $u\in\mathcal{U}$, recall the
definitions of $\mathrm{End}(x)$ given in Step 8. Recall also the definitions
of $P$, $P^{\prime}$ and $C^{\bullet}$ from Step 9. Combining all the previous
steps, we claim that the following hold (conditioned on the events
$\mathcal{E}_{1}^{*},\ldots,\mathcal{E}_{8}^{*}$, which occur a.a.s.).

  1. $(\mathrm{C}1)$

$\Delta(T^{\prime\prime})\leq 12D$.

  2. $(\mathrm{C}2)$

Any vertex $x\in R^{\prime}\cap V(T^{\prime\prime})$ is a leaf of
$T^{\prime\prime}$. Furthermore, if $x\in R^{\prime}\cap V(T^{\prime\prime})$,
then $x\notin V(T)$ and its unique neighbour $x^{\prime}$ in
$T^{\prime\prime}$ satisfies that $x^{\prime}\in Z(x)$ (where $Z(x)$ is as
defined in Step 7).

  3. $(\mathrm{C}3)$

$B_{I}^{5}(\mathcal{U}_{I})\cap V(T^{\prime\prime})=\varnothing$.

  4. $(\mathrm{C}4)$

For all $x\in V(I)$ we have that
$|\mathcal{C}_{x}\cap\mathcal{C}^{\prime\prime\prime}|\geq(1-3/2\ell^{4})n$.

  5. $(\mathrm{C}5)$

For each $x\in V_{\mathrm{sc}}$ and $i\in[K]$, there is a collection
$\mathcal{C}^{\mathrm{sc}}_{1}(x,i)$ of $2^{s+1}\Psi$ absorbing $\ell$-cube
pairs $(C^{l}(x,i,k),C^{r}(x,i,k))$ for $x$ in $I$ (defined in Step 9), each
of which is associated with some edge $e\in M(A_{i}(x))$. In particular,
$(C^{l}(x,i,k),C^{r}(x,i,k))$ is as described in $(\mathrm{AB}1)$ (recall also
$(\mathrm{AB}2)$), that is, there are two absorbing $\ell$-cube pairs
$(C^{l}_{1}(x,i,k),C^{r}_{1}(x,i,k))$ and
$(C^{l}_{2}(x,i,k),C^{r}_{2}(x,i,k))$ in $H\cup G$, associated with $e\in
M(A_{i}(x))$, for the clones $x_{1}$ and $x_{2}$ of $x$ which correspond to
$(x,i)$. Moreover, each of these absorbing $\ell$-cube pairs
$(C^{l}(x,i,k),C^{r}(x,i,k))$ satisfies the following:

    1. $(\mathrm{C}5.1)$

$(C^{l}_{1}(x,i,k),C^{r}_{1}(x,i,k))\cup(C^{l}_{2}(x,i,k),C^{r}_{2}(x,i,k))-V(\mathcal{M}_{x})\subseteq
Q^{\prime}$;

    2. $(\mathrm{C}5.2)$

the tips of $C^{l}(x,i,k)$ and $C^{r}(x,i,k)$ lie in $R^{\prime}\setminus
V(T^{\prime\prime})$;

    3. $(\mathrm{C}5.3)$

$C^{l}(x,i,k),C^{r}(x,i,k)\in\mathcal{C}^{\prime\prime}\cap\mathcal{C}^{\prime\prime\prime}$,
and

    4. $(\mathrm{C}5.4)$

for any $x^{\prime}\in V_{\mathrm{sc}}$, $i^{\prime}\in[K]$ and
$k^{\prime}\in[2^{s+1}\Psi]$ with
$(x^{\prime},i^{\prime},k^{\prime})\neq(x,i,k)$, we have that $C^{l}(x,i,k)$,
$C^{r}(x,i,k)$, $C^{l}(x^{\prime},i^{\prime},k^{\prime})$ and
$C^{r}(x^{\prime},i^{\prime},k^{\prime})$ are vertex-disjoint.

  6. $(\mathrm{C}6)$

For each $x\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ and
$i\in[K]$, there is a collection $\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$ of
$2^{s+1}\Psi$ absorbing $\ell$-cube pairs $(C^{l}(x,i,k),C^{r}(x,i,k))$ for
$x$ in $I$ (defined in Step 10), each of which is associated with an edge
$e\in M(A_{i}(x))$. In particular, $(C^{l}(x,i,k),C^{r}(x,i,k))$ is as
described in $(\mathrm{AB}1)$ (recall also $(\mathrm{AB}2)$), that is, there
are two absorbing $\ell$-cube pairs $(C^{l}_{1}(x,i,k),C^{r}_{1}(x,i,k))$ and
$(C^{l}_{2}(x,i,k),C^{r}_{2}(x,i,k))$ in $H\cup G$, associated with $e\in
M(A_{i}(x))$, for the clones $x_{1}$ and $x_{2}$ of $x$ which correspond to
$(x,i)$. Moreover, each of these absorbing $\ell$-cube pairs
$(C^{l}(x,i,k),C^{r}(x,i,k))$ satisfies the following:

    1. $(\mathrm{C}6.1)$

$(C^{l}_{1}(x,i,k),C^{r}_{1}(x,i,k))\cup(C^{l}_{2}(x,i,k),C^{r}_{2}(x,i,k))-V(\mathcal{M}_{x})\subseteq
Q^{\prime}$;

    2. $(\mathrm{C}6.2)$

the tips of $C^{l}(x,i,k)$ and $C^{r}(x,i,k)$ lie in $R^{\prime}$;

    3. $(\mathrm{C}6.3)$

$C^{l}(x,i,k),C^{r}(x,i,k)\in\mathcal{C}^{\prime\prime}\cap\mathcal{C}^{\prime\prime\prime}$;

    4. $(\mathrm{C}6.4)$

for any $x^{\prime}\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$,
$i^{\prime}\in[K]$ and $k^{\prime}\in[2^{s+1}\Psi]$ with
$(x^{\prime},i^{\prime},k^{\prime})\neq(x,i,k)$, we have that $C^{l}(x,i,k)$,
$C^{r}(x,i,k)$, $C^{l}(x^{\prime},i^{\prime},k^{\prime})$ and
$C^{r}(x^{\prime},i^{\prime},k^{\prime})$ are vertex-disjoint, and

    5. $(\mathrm{C}6.5)$

both $C^{l}(x,i,k)$ and $C^{r}(x,i,k)$ are vertex-disjoint from all cubes of
absorbing $\ell$-cube pairs in $\mathcal{C}^{\mathrm{sc}}_{1}$.

  7. $(\mathrm{C}7)$

For every $x\in\mathcal{U}$ and every $z\in\mathrm{End}(x)$, there exists a
collection of cubes $\mathcal{C}^{\prime\prime}(z)$ in $I(Q^{\prime})$ with
$|\mathcal{C}^{\prime\prime}(z)|=20\ell$ which satisfies the following
properties:

    1. $(\mathrm{C}7.1)$

for every $C\in\mathcal{C}^{\prime\prime}(z)$, we have that $z\in V(C)$;

    2. $(\mathrm{C}7.2)$

for every $C\in\mathcal{C}^{\prime\prime}(z)$, the molecule $\mathcal{M}_{C}$
is bonded in $Q^{\prime}$;

    3. $(\mathrm{C}7.3)$

every $C\in\mathcal{C}^{\prime\prime}(z)$ meets $T^{\prime\prime}$;

    4. $(\mathrm{C}7.4)$

for every $C_{1},C_{2}\in\mathcal{C}^{\prime\prime}(z)$, we have $V(C_{1})\cap
V(C_{2})=\\{z\\}$, and

    5. $(\mathrm{C}7.5)$

for every $C^{*}\in\mathcal{C}^{\mathrm{sc}}_{1}$ and
$C\in\mathcal{C}^{\prime\prime}(z)$, we have $V(C)\cap V(C^{*})=\varnothing$.

  8. $(\mathrm{C}8)$

$C^{\bullet}$ intersects $V(T)\cap V(T^{\prime\prime})$ and is different from
all cubes described in $(\mathrm{C}5)$, $(\mathrm{C}6)$ and $(\mathrm{C}7)$.

Indeed, $(\mathrm{C}1)$ is given by (9.7). $(\mathrm{C}2)$ holds by
$(\mathrm{ET}3)$ and the fact that $P^{\prime}\cap
V(T^{\prime\prime})=\varnothing$. $(\mathrm{C}3)$ follows directly by (9.6).
$(\mathrm{C}4)$ follows by combining $(\mathrm{N}1)$, the conditioning on
$\mathcal{E}_{5}^{*}$, (9.9) and $(\mathrm{R}3)$. $(\mathrm{C}5)$ follows from
the construction of $P$ and $T^{\prime\prime}$ in Step 9. Indeed,
$(\mathrm{C}5)$$(\mathrm{C}5.1)$ follows from the definition of $Q^{\prime}$
combined with $(\mathrm{AB}1)$, and $(\mathrm{C}5)$$(\mathrm{C}5.2)$ holds by
the definition of $R^{\prime}$ and $T^{\prime\prime}$ combined with
$(\mathrm{AB}1)$, while $(\mathrm{C}5)$$(\mathrm{C}5.3)$ follows because of
the definition of the set $M(A_{i}(x))$ in $(\mathrm{AB}2)$ and
$(\mathrm{AB}3)$, and $(\mathrm{C}5)$$(\mathrm{C}5.4)$ holds by
$(\mathrm{CD})$. Consider now $(\mathrm{C}6)$. For each $x\in
V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ and $i\in[K]$, consider
$\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$. All absorbing $\ell$-cube pairs of
$\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$ satisfy $(\mathrm{C}6)$$(\mathrm{C}6.1)$
and $(\mathrm{C}6)$$(\mathrm{C}6.2)$ by the definition of $Q^{\prime}$,
$(\mathrm{AB}1)$ and $(\mathrm{AB}4)$. Similarly, they satisfy
$(\mathrm{C}6)$$(\mathrm{C}6.3)$ by $(\mathrm{AB}2)$, $(\mathrm{AB}3)$ and the
fact that, by $(\mathrm{AB}4)$, their intersection with $T^{\prime\prime}$
contains their intersection with $T^{\prime}$. Moreover,
$(\mathrm{C}6)$$(\mathrm{C}6.4)$ holds by 9.3, and
$(\mathrm{C}6)$$(\mathrm{C}6.5)$ holds because of $(\mathrm{AB}4)$. Now,
$(\mathrm{C}7)$ holds by 9.1 and $(\mathrm{T}4)$. Indeed, let
$\mathcal{C}^{\prime\prime}(z)$ be the collection of cubes given by 9.1, so
$(\mathrm{C}7)$$(\mathrm{C}7.1)$, $(\mathrm{C}7)$$(\mathrm{C}7.2)$ and
$(\mathrm{C}7)$$(\mathrm{C}7.4)$ follow directly.
$(\mathrm{C}7)$$(\mathrm{C}7.3)$ follows by using again the observation that,
by $(\mathrm{T}4)$ and the construction of $P$, for any $x\in\mathcal{U}_{I}$,
we have that $T^{\prime}$ and $T^{\prime\prime}$ coincide in
$B_{I}^{2\ell}(x)$. Now recall that, by $(\mathrm{T}4)$, all vertices
$x\in\mathcal{U}_{I}$ are at distance at least $5\ell$ from $V_{\mathrm{sc}}$,
so $(\mathrm{C}7)$$(\mathrm{C}7.5)$ follows by construction. Finally, consider
$(\mathrm{C}8)$. The fact that $C^{\bullet}$ intersects $V(T)\cap
V(T^{\prime\prime})$ follows by its definition in Step 9, as does the fact
that it is different from all cubes described in $(\mathrm{C}5)$. The fact
that it is different from all cubes in $(\mathrm{C}6)$ follows by
$(\mathrm{AB}4)$. Finally, the fact that it is different from the cubes in
$(\mathrm{C}7)$ follows since ${\rm
dist}(V(C^{\bullet}),\mathcal{U}_{I})\geq\ell$ by the definition of
$C^{\bullet}$ in Step 9.

Step 11: Fixing special absorbing structures. From this point onward, every
step will be deterministic. Let $F\subseteq\mathcal{Q}^{n}$ be any graph with
$\Delta(F)\leq\Psi$ which is $(\mathcal{U},\ell,s)$-good, that is, for each
$x\in\mathcal{U}$, the set $E_{F}(x)\coloneqq\\{e\in E(F):e\cap
N_{\mathcal{Q}^{n}}(x)\neq\varnothing\\}$ satisfies the following:

  1. ($F^{enumi}$)

for each layer $L$ of $\mathcal{Q}^{n}$ and all $d\in\mathcal{D}(L)$, we have
$|\\{e\in E_{F}(x):\mathcal{D}(e)=d\\}|\leq n/\ell$.

Let $H^{\prime}\subseteq\mathcal{Q}^{n}$ be any graph such that, for every
$x\in\mathcal{U}$, we have $d_{H^{\prime}}(x)\geq 2$. For each
$x\in\mathcal{U}$, let $\\{x,x+a(x)\\},\\{x,x+b(x)\\}\in E(H^{\prime})$, where
$a(x),b(x)\in\mathcal{D}(\mathcal{Q}^{n})$. Our goal is to find a
$(\mathcal{U},\ell^{2},s)$-good Hamilton cycle in $((H\cup G)\setminus F)\cup
H^{\prime}\cup Q^{\prime}$ which, for each $x\in\mathcal{U}$, contains the
edges $\\{x,x+a(x)\\}$ and $\\{x,x+b(x)\\}$. Recall that
$\mathfrak{C}^{\prime}(x,a(x),b(x))$ was defined in Step 8.

######  Claim 9.5.

For every $x\in\mathcal{U}$, there exists an $(x,a(x),b(x))$-consistent system
of paths $\mathit{CS}(x)\in\mathfrak{C}^{\prime}(x,a(x),b(x))$ such that
$(E(\mathit{CS}(x))\setminus\\{\\{x,x+a(x)\\},\\{x,x+b(x)\\}\\})\cap
E(F)=\varnothing$.

###### Proof.

Suppose $x\in V(L)$, for some layer $L$. Suppose first that $x+a(x),x+b(x)\in
V(L)$. Thus, we must show the existence of an $(x,a(x),b(x))$-consistent
system of paths of Type I in $\mathfrak{C}^{\prime}(x,a(x),b(x))$ with the
desired property. Recall all the notation for consistent systems of paths
introduced in Section 9.1, as well as Definition 9.3. By (CS), there is a
collection $\mathcal{D}^{(2)}(x,a(x),b(x))$ of at least $\gamma n/2$ disjoint
pairs of distinct directions $c,d\in\mathcal{D}(L)\setminus\\{a(x),b(x)\\}$
such that, for each $(c,d)\in\mathcal{D}^{(2)}(x,a(x),b(x))$, there is a
collection $\mathcal{D}^{(4)}(x,a(x),b(x),c,d)$ of at least $\gamma n/2$
disjoint $4$-tuples of distinct directions in
$\mathcal{D}(L)\setminus\\{a(x),b(x),c,d\\}$ satisfying the following: for
each $(c,d)\in\mathcal{D}^{(2)}(x,a(x),b(x))$ and each
$(d_{1},d_{2},d_{3},d_{4})\in\mathcal{D}^{(4)}(x,a(x),b(x),c,d)$,
$\mathfrak{C}^{\prime}(x,a(x),b(x))$ contains the $(x,a(x),b(x))$-consistent
system of paths $\mathit{CS}(c,d,d_{1},d_{2},d_{3},d_{4})$ defined as in
Section 9.1. We will now show that there are many such consistent systems of
paths which avoid $F$.

The choice of $(c,d)\in\mathcal{D}^{(2)}(x,a(x),b(x))$ determines six edges of
the consistent system of paths: $e_{1}\coloneqq\\{f(x+a(x)),f(x+a(x)+d)\\}$,
$e_{2}\coloneqq\\{f(x+b(x)),f(x+b(x)+c)\\}$,
$e_{3}\coloneqq\\{f(x+c),f(x)\\}$, $e_{4}\coloneqq\\{f(x),f(x+d)\\}$,
$e_{5}\coloneqq\\{x+c,x+c+b(x)\\}$ and $e_{6}\coloneqq\\{x+d,x+d+a(x)\\}$.
Since $f(x)$, $f(x+a(x))$ and $f(x+b(x))$ are fixed and $\Delta(F)\leq\Psi$,
for each $i\in[4]$ there are at most $\Psi$ choices of
$(c,d)\in\mathcal{D}^{(2)}(x,a(x),b(x))$ such that $e_{i}\in E(F)$.
Furthermore, by ($F^{enumi}$), for each $i\in\\{5,6\\}$ there are at most
$n/\ell$ choices $(c,d)\in\mathcal{D}^{(2)}(x,a(x),b(x))$ such that $e_{i}\in
E(F)$. Thus, there exist at least $\gamma n/2-4\Psi-2n/\ell\geq\gamma n/4$
choices $(c,d)\in\mathcal{D}^{(2)}(x,a(x),b(x))$ such that $e_{i}\in
E(H)\setminus E(F)$ for all $i\in[6]$. For any such choice of $(c,d)$, the
choice of $(d_{1},d_{2},d_{3},d_{4})\in\mathcal{D}^{(4)}(x,a(x),b(x),c,d)$ now
determines the remaining eight edges of an $(x,a(x),b(x))$-consistent system
of paths, each with a unique endpoint in
$\\{x+a(x),x+b(x),f(x+b(x)),x+c,f(x+c),f(x+d),x+d,f(x+a(x))\\}$. It now
follows by the fact that $\Delta(F)\leq\Psi$ that there are at most $8\Psi$
choices of $(d_{1},d_{2},d_{3},d_{4})\in\mathcal{D}^{(4)}(x,a(x),b(x),c,d)$
such that some of these eight edges lies in $E(F)$. In particular, we may fix
a consistent system of paths
$\mathit{CS}(x)\in\mathfrak{C}^{\prime}(x,a(x),b(x))$ which satisfies the
statement of the claim.

The cases where $x+a(x)\notin L$, $x+b(x)\in L$ and where $x+a(x),x+b(x)\notin
L$ can be shown similarly. ∎

Note that $\mathit{CS}(x)\subseteq(H\setminus F)\cup H^{\prime}$ for each
$x\in\mathcal{U}$.

######  Claim 9.6.

For every $x\in\mathcal{U}$, we can extend $\mathit{CS}(x)$ into an
$(x,a(x),b(x))$-special absorbing structure $\mathit{SA}(x)$ such that the
following hold:

  1. $(\mathrm{SA}_{\mathrm{i}})$

for every $C\in\mathbf{C}(\mathit{SA}(x))$, we have that
$\mathcal{M}_{C}\subseteq Q^{\prime}$ and $\mathcal{M}_{C}$ is bonded in
$Q^{\prime}$, and

  2. $(\mathrm{SA}_{\mathrm{ii}})$

every $C\in\mathbf{C}(\mathit{SA}(x))$ meets $T^{\prime\prime}$.

###### Proof.

For each $x\in\mathcal{U}$, we iterate through each
$z\in\mathrm{endmol}(\mathit{CS}(x))$ fixing a cube
$C(z)\in\mathcal{C}^{\prime\prime}(z)$. This will then determine
$\mathbf{C}(\mathit{SA}(x))$, by taking the appropriate clones of $C(z)$. To
see that this can be done, note that $|\mathrm{endmol}(\mathit{CS}(x))|\leq
6$. For each $z\in\mathrm{endmol}(\mathit{CS}(x))$, by $(\mathrm{C}7)$, there
exist at least $20\ell$ choices of $C(z)\in\mathcal{C}^{\prime\prime}(z)$ for
which $(\mathrm{SA}_{\mathrm{i}})$ and $(\mathrm{SA}_{\mathrm{ii}})$ hold.
Finally, by $(\mathrm{C}7)$$(\mathrm{C}7.4)$ it follows that we can fix
$C(z)\in\mathcal{C}^{\prime\prime}(z)$ such that
$\mathcal{D}(C(z))\cap\mathcal{D}(\mathit{CS}(x))=\varnothing$. In particular,
this implies that $C(z)$ is vertex-disjoint from all $C(z^{\prime})$ already
fixed with $z\neq z^{\prime}\in\mathrm{endmol}(\mathit{CS}(x))$ and,
therefore, this process forms a valid extension of $\mathit{CS}(x)$ into an
$(x,a(x),b(x))$-special absorbing structure. ∎

For each $x\in\mathcal{U}$, let $\mathit{SA}(x)$ be an $(x,a(x),b(x))$-special
absorbing structure which extends $\mathit{CS}(x)$, as determined by 9.6. Note
that, by $(\mathrm{R}3)$ and the fact that $V(\mathit{SA}(x))\subseteq
B_{\mathcal{Q}^{n}}^{2\ell}(x)$, the special absorbing structures in the
collection $\\{\mathit{SA}(x):x\in\mathcal{U}\\}$ are pairwise vertex-
disjoint. Denote by
$\mathit{SA}^{v}\coloneqq\bigcup_{x\in\mathcal{U}}V(\mathit{SA}(x))$. Recall
that, for any $C\in\mathbf{C}(\mathit{SA}(x))$, $C_{I}\subseteq I$ denotes the
cube which $C$ is a clone of. Given any tree $T^{\bullet}\subseteq I$ and any
$x\in\mathcal{U}$, we say that $\mathit{SA}(x)$ _meets $T^{\bullet}$_ if, for
all $C\in\mathbf{C}(\mathit{SA}(x))$, we have $V(C_{I})\cap
V(T^{\bullet})\neq\varnothing$.

Recall that $\mathcal{C}^{\prime}$ and $\mathcal{C}^{\prime\prime}$ were
defined in Step 6. Let
$\mathcal{C}_{1}^{*}\coloneqq\\{C\in\mathcal{C}^{\prime}:V(\mathcal{M}_{C})\cap\mathit{SA}^{v}\neq\varnothing\\}$.
Note that, by $(\mathrm{R}3)$,

  1. $(\mathrm{CB})$

for each $x\in\mathcal{U}$, there are at most $2^{2\ell}$ $\ell$-cubes
$C\in\mathcal{C}^{*}_{1}$ such that $V(C)\cap B^{10\ell}(x)\neq\varnothing$.

Let
$\mathcal{C}^{\prime}_{1}\coloneqq\mathcal{C}^{\prime}\setminus\mathcal{C}_{1}^{*}$
and
$\mathcal{C}^{\prime\prime}_{1}=\mathcal{C}^{\prime\prime}\setminus\mathcal{C}^{*}_{1}$.
We now define a tree $T^{\prime\prime\prime}\subseteq T^{\prime\prime}$ in the
following way. Consider each $x\in R^{\prime}\cap V(T^{\prime\prime})$ such
that $x\in V(C)$ for some $C\in\mathcal{C}^{\prime}_{1}$. By $(\mathrm{C}2)$,
we have that $x$ has a unique neighbour $x^{\prime}$ in $T^{\prime\prime}$,
and $x^{\prime}\in Z(x)$. By the definition of $Z(x)$ (see Step 7), it follows
that $x^{\prime}\in V(C^{\prime})$ for some
$C^{\prime}\in\mathcal{C}^{\prime\prime}$. If
$C^{\prime}\notin\mathcal{C}^{\prime\prime}_{1}$, then we remove $x$ from
$T^{\prime\prime}$. We denote the resulting tree by $T^{\prime\prime\prime}$.
Let
$\mathcal{C}^{\prime\prime\prime}_{1}\coloneqq\\{C\in\mathcal{C}^{\prime}_{1}:V(C)\cap
V(T^{\prime\prime\prime})\neq\varnothing\\}$. By using
$(\mathrm{C}1)$–$(\mathrm{C}6)$, the definition of $\mathcal{C}^{\prime}_{1}$,
$\mathcal{C}^{\prime\prime}_{1}$ and $\mathcal{C}^{\prime\prime\prime}_{1}$,
the construction of $T^{\prime\prime\prime}$, and the maximum degree of $F$,
we claim that the following now hold.

  1. $(\mathrm{C^{\prime}}1)$

$\Delta(T^{\prime\prime\prime})\leq 12D$.

  2. $(\mathrm{C^{\prime}}2)$

Any vertex $x\in R^{\prime}\cap V(T^{\prime\prime\prime})$ is a leaf of
$T^{\prime\prime\prime}$. Furthermore, if $x\in R^{\prime}\cap
V(T^{\prime\prime\prime})$, then $x\notin V(T)$ and its unique neighbour
$x^{\prime}$ in $T^{\prime\prime\prime}$ satisfies that $x^{\prime}\in
N_{I}(x)\cap
V(T)\cap(\bigcup_{C\in\mathcal{C}^{\prime\prime}_{1}}V(C))\subseteq Z(x)$.

  3. $(\mathrm{C^{\prime}}3)$

$B_{I}^{5}(\mathcal{U}_{I})\cap V(T^{\prime\prime\prime})=\varnothing$.

  4. $(\mathrm{C^{\prime}}4)$

For all $x\in V(I)$ we have that
$|\mathcal{C}_{x}\cap\mathcal{C}^{\prime\prime\prime}_{1}|\geq(1-2/\ell^{4})n$.

  5. $(\mathrm{C^{\prime}}5)$

For each $x\in V_{\mathrm{sc}}$ and $i\in[K]$, there is an absorbing
$\ell$-cube pair $(C^{l}(x,i),C^{r}(x,i))$ for $x$ in $I$, which is associated
with some edge $e\in M(A_{i}(x))$. In particular, $(C^{l}(x,i),C^{r}(x,i))$ is
such that there are two absorbing $\ell$-cube pairs
$(C^{l}_{1}(x,i),C^{r}_{1}(x,i))$ and $(C^{l}_{2}(x,i),C^{r}_{2}(x,i))$ in
$H\cup G$, associated with $e\in M(A_{i}(x))$, for the clones $x_{1}$ and
$x_{2}$ of $x$ which correspond to $(x,i)$. Additionally, each of these
absorbing $\ell$-cube pairs $(C^{l}(x,i),C^{r}(x,i))$ satisfies the following:

    1. $(\mathrm{C^{\prime}}5.1)$

$(C^{l}_{1}(x,i),C^{r}_{1}(x,i))\cup(C^{l}_{2}(x,i),C^{r}_{2}(x,i))-V(\mathcal{M}_{x})\subseteq
Q^{\prime}$;

    2. $(\mathrm{C^{\prime}}5.2)$

the tips $x^{l}$ of $C^{l}(x,i)$ and $x^{r}$ of $C^{r}(x,i)$ lie in
$R^{\prime}\setminus V(T^{\prime\prime\prime})$, and
$\\{x,x^{l}\\},\\{x,x^{r}\\}\notin E(F_{I})$; in particular, the tips
$x_{1}^{l},x_{1}^{r}$ of $(C^{l}_{1}(x,i),C^{r}_{1}(x,i))$ and
$x_{2}^{l},x_{2}^{r}$ of $(C^{l}_{2}(x,i),C^{r}_{2}(x,i))$ satisfy that
$\\{x_{1},x_{1}^{l}\\},\\{x_{1},x_{1}^{r}\\},\\{x_{2},x_{2}^{l}\\},\\{x_{2},x_{2}^{r}\\}\in
E((H\cup G)\setminus F)$;

    3. $(\mathrm{C^{\prime}}5.3)$

$C^{l}(x,i),C^{r}(x,i)\in\mathcal{C}^{\prime\prime}_{1}\cap\mathcal{C}^{\prime\prime\prime}_{1}$,
and

    4. $(\mathrm{C^{\prime}}5.4)$

for any $x^{\prime}\in V_{\mathrm{sc}}$ and $i^{\prime}\in[K]$ with
$(x^{\prime},i^{\prime})\neq(x,i)$, we have that $C^{l}(x,i)$, $C^{r}(x,i)$,
$C^{l}(x^{\prime},i^{\prime})$ and $C^{r}(x^{\prime},i^{\prime})$ are vertex-
disjoint.

Let $\mathcal{C}^{\mathrm{sc}}$ denote the collection of these absorbing
$\ell$-cube pairs.

  6. $(\mathrm{C^{\prime}}6)$

For each $x\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ and
$i\in[K]$, there is an absorbing $\ell$-cube pair $(C^{l}(x,i),C^{r}(x,i))$
for $x$ in $I$, which is associated with an edge $e\in M(A_{i}(x))$. In
particular, $(C^{l}(x,i),C^{r}(x,i))$ is such that there are two absorbing
$\ell$-cube pairs $(C^{l}_{1}(x,i),C^{r}_{1}(x,i))$ and
$(C^{l}_{2}(x,i),C^{r}_{2}(x,i))$ in $H\cup G$, associated with $e\in
M(A_{i}(x))$, for the clones $x_{1}$ and $x_{2}$ of $x$ which correspond to
$(x,i)$. Moreover, each of these absorbing $\ell$-cube pairs
$(C^{l}(x,i),C^{r}(x,i))$ satisfies the following:

    1. $(\mathrm{C^{\prime}}6.1)$

$(C^{l}_{1}(x,i),C^{r}_{1}(x,i))\cup(C^{l}_{2}(x,i),C^{r}_{2}(x,i))-V(\mathcal{M}_{x})\subseteq
Q^{\prime}$;

    2. $(\mathrm{C^{\prime}}6.2)$

the tips $x^{l}$ of $C^{l}(x,i)$ and $x^{r}$ of $C^{r}(x,i)$ lie in
$R^{\prime}$, and $\\{x,x^{l}\\},\\{x,x^{r}\\}\notin E(F_{I})$; in particular,
the tips $x_{1}^{l},x_{1}^{r}$ of $(C^{l}_{1}(x,i),C^{r}_{1}(x,i))$ and
$x_{2}^{l},x_{2}^{r}$ of $(C^{l}_{2}(x,i),C^{r}_{2}(x,i))$ satisfy that
$\\{x_{1},x_{1}^{l}\\},\\{x_{1},x_{1}^{r}\\},\\{x_{2},x_{2}^{l}\\},\\{x_{2},x_{2}^{r}\\}\in
E((H\cup G)\setminus F)$;

    3. $(\mathrm{C^{\prime}}6.3)$

$C^{l}(x,i),C^{r}(x,i)\in\mathcal{C}^{\prime\prime}_{1}\cap\mathcal{C}^{\prime\prime\prime}_{1}$;

    4. $(\mathrm{C^{\prime}}6.4)$

for any $x^{\prime}\in V_{\mathrm{abs}}^{\prime}\setminus V_{\mathrm{sc}}$ and
$i^{\prime}\in[K]$ with $(x^{\prime},i^{\prime})\neq(x,i)$, we have that
$C^{l}(x,i)$, $C^{r}(x,i)$, $C^{l}(x^{\prime},i^{\prime})$ and
$C^{r}(x^{\prime},i^{\prime})$ are vertex-disjoint, and

    5. $(\mathrm{C^{\prime}}6.5)$

both $C^{l}(x,i)$ and $C^{r}(x,i)$ are vertex-disjoint from all cubes of
absorbing $\ell$-cube pairs in $\mathcal{C}^{\mathrm{sc}}$.

Let $\mathcal{C}^{\neg\mathrm{sc}}$ denote the set of these absorbing
$\ell$-cube pairs.

  7. $(\mathrm{C^{\prime}}7)$

For every $x\in\mathcal{U}$, there is an $(x,a(x),b(x))$-consistent system of
paths $\mathit{CS}(x)$ in $(H\setminus F)\cup H^{\prime}$ which extends into
an $(x,a(x),b(x))$-special absorbing structure $\mathit{SA}(x)$ which meets
$T^{\prime\prime\prime}$ and with the property that, for every
$C\in\mathbf{C}(SA(x,a,b))$, we have that $\mathcal{M}_{C_{I}}\subseteq
Q^{\prime}$ and $\mathcal{M}_{C_{I}}$ is bonded in $Q^{\prime}$. Moreover,
$\\{x,x+a(x)\\},\\{x,x+b(x)\\}\in E(H^{\prime})$.

  8. $(\mathrm{C^{\prime}}8)$

$C^{\bullet}$ intersects $V(T)\cap V(T^{\prime\prime\prime})$ (so, in
particular, $C^{\bullet}\in\mathcal{C}^{\prime\prime\prime}_{1}$) and is
different from all cubes described in $(\mathrm{C^{\prime}}5)$,
$(\mathrm{C^{\prime}}6)$ and $(\mathrm{C^{\prime}}7)$.

  9. $(\mathrm{C^{\prime}}9)$

$\bigcup_{C\in\mathcal{C}^{\prime\prime\prime}\setminus\mathcal{C}^{\prime\prime\prime}_{1}}V(C)\subseteq
B_{I}^{3\ell}(\mathcal{U}_{I})$.

Indeed, since $T^{\prime\prime\prime}\subseteq T^{\prime\prime}$,
$(\mathrm{C^{\prime}}1)$–$(\mathrm{C^{\prime}}3)$ follow immediately by
$(\mathrm{C}1)$–$(\mathrm{C}3)$, respectively. $(\mathrm{C^{\prime}}4)$
follows from $(\mathrm{C}4)$, $(\mathrm{R}3)$ and $(\mathrm{CB})$. Now, for
each $x\in V_{\mathrm{sc}}$ and $i\in[K]$, consider the set
$\mathcal{C}^{\mathrm{sc}}_{1}(x,i)$ described in $(\mathrm{C}5)$. We first
remove from this set all absorbing $\ell$-cube pairs any of whose cubes do not
belong to $\mathcal{C}^{\prime}_{1}$. Then, we remove all absorbing
$\ell$-cube pairs any of whose cubes do not intersect
$T^{\prime\prime\prime}$. Finally, we remove all absorbing $\ell$-cube pairs
such that any of the edges joining its tips to $x$ belong to $F_{I}$. Observe
that by $(\mathrm{CB})$ and $(\mathrm{C^{\prime}}1)$ it follows that, for any
$y\in V(I)$, we have $|B_{I}^{10\ell}(y)\cap(V(T^{\prime\prime})\setminus
V(T^{\prime\prime\prime}))|\leq 12D\cdot 2^{3\ell}$. Using this fact,
$(\mathrm{CB})$, and the fact that $\Delta(F)\leq\Psi$ (and, thus,
$\Delta(F_{I})\leq 2^{s}\Psi$), it follows that there is at least one
absorbing $\ell$-cube pair remaining in the collection. Let
$(C^{l}(x,i),C^{r}(x,i))$ be such an absorbing $\ell$-cube pair. Then,
$(\mathrm{C^{\prime}}5)$$(\mathrm{C^{\prime}}5.2)$ and
$(\mathrm{C^{\prime}}5)$$(\mathrm{C^{\prime}}5.3)$ hold by the choice above,
and $(\mathrm{C^{\prime}}5)$$(\mathrm{C^{\prime}}5.1)$ and
$(\mathrm{C^{\prime}}5)$$(\mathrm{C^{\prime}}5.4)$ hold by
$(\mathrm{C}5)$$(\mathrm{C}5.1)$ and $(\mathrm{C}5)$$(\mathrm{C}5.4)$,
respectively. For each $x\in V_{\mathrm{abs}}^{\prime}\setminus
V_{\mathrm{sc}}$ and $i\in[K]$, we proceed similarly from the set
$\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$ to fix an absorbing $\ell$-cube pair
$(C^{l}(x,i),C^{r}(x,i))\in\mathcal{C}^{\mathrm{abs}}_{1}(x,i)$ which
satisfies $(\mathrm{C^{\prime}}6)$$(\mathrm{C^{\prime}}6.2)$ and
$(\mathrm{C^{\prime}}6)$$(\mathrm{C^{\prime}}6.3)$. Then,
$(\mathrm{C^{\prime}}6)$$(\mathrm{C^{\prime}}6.1)$,
$(\mathrm{C^{\prime}}6)$$(\mathrm{C^{\prime}}6.4)$ and
$(\mathrm{C^{\prime}}6)$$(\mathrm{C^{\prime}}6.5)$ hold by
$(\mathrm{C}6)$$(\mathrm{C}6.1)$, $(\mathrm{C}6)$$(\mathrm{C}6.4)$ and
$(\mathrm{C}6)$$(\mathrm{C}6.5)$, respectively. Furthermore,
$(\mathrm{C^{\prime}}7)$ holds by 9.5, 9.6 and the construction of
$T^{\prime\prime\prime}$ above. (Indeed, to see that each $SA(x)$ still meets
$T^{\prime\prime\prime}$, note that $(V(T^{\prime\prime})\setminus
V(T^{\prime\prime\prime}))\cap\mathit{SA}^{v}=\varnothing$.) For
$(\mathrm{C^{\prime}}8)$, by construction $C^{\bullet}\in\mathcal{C}^{\prime}$
and $V(C^{\bullet})\cap B^{3\ell/2}_{I}(\mathcal{U}_{I})=\varnothing$.
Therefore, $C^{\bullet}\in\mathcal{C}^{\prime}_{1}$. The fact that
$C^{\bullet}$ intersects $V(T)\cap V(T^{\prime\prime\prime})$ follows by
$(\mathrm{C}8)$ and the fact that, in constructing $T^{\prime\prime\prime}$,
none of the leaves which are removed are vertices of $T$. Thus, in particular,
$C^{\bullet}\in\mathcal{C}^{\prime\prime\prime}_{1}$. The rest of
$(\mathrm{C^{\prime}}8)$ follows immediately from $(\mathrm{C}8)$. Finally,
$(\mathrm{C^{\prime}}9)$ follows by the definition of $\mathcal{C}^{*}_{1}$.
Indeed, consider the set $\mathit{SA}^{v}_{I}\subseteq V(I)$ of vertices such
that each vertex in $\mathit{SA}^{v}$ is a clone of some vertex in
$\mathit{SA}^{v}_{I}$. It follows by construction (see Section 9.1) that for
any $x\in\mathit{SA}^{v}_{I}$ we have ${\rm
dist}(x,\mathcal{U}_{I})\leq\ell+2$. The claim follows since any $\ell$-cube
$C\in\mathcal{C}^{*}_{1}$ must intersect $\mathit{SA}^{v}_{I}$ and any two
vertices in $C$ are at distance at most $\ell$.

Let
$\mathcal{C}^{\prime}_{2}\coloneqq\bigcup_{x\in\mathcal{U}}\\{C_{I}:C\in\mathbf{C}(\mathit{SA}(x))\\}$
and $R^{\prime\prime}\coloneqq
R^{\prime}\setminus\bigcup_{C\in\mathcal{C}^{\prime}_{2}}V(C)$. Finally, let
$\mathcal{C}^{\prime\prime\prime}_{3}\coloneqq\mathcal{C}^{\prime\prime\prime}_{1}\cup\mathcal{C}^{\prime}_{2}$.
Note that, by construction, any two cubes in
$\mathcal{C}^{\prime\prime\prime}_{3}$ are vertex-disjoint.

Step 12: Constructing auxiliary trees $\bm{T^{*}}$ and $\bm{\tau_{0}}$. Let
$T^{*}$ be obtained from $T^{\prime\prime\prime}$ by removing all leaves of
$T^{\prime\prime\prime}$ which lie in $R^{\prime\prime}$. In particular, by
$(\mathrm{C^{\prime}}2)$ and $(\mathrm{C^{\prime}}8)$, we have that
$C^{\bullet}$ intersects $T^{*}$.

We now construct an auxiliary tree $\tau_{0}$, which will be used in the
construction of an almost spanning cycle. The construction of $\tau_{0}$ is
identical to that in Step 10 of the proof of Theorem 8.1, except that
$\mathcal{C}^{\prime\prime\prime}_{3}$ plays the role of
$\mathcal{C}^{\prime}$ in the definition of $\Gamma_{1}\coloneqq
T^{*}\cup\bigcup_{C\in\mathcal{C}^{\prime\prime\prime}_{3}}C$ and the
subsequent steps, and that, for the depth-first search on $\Gamma^{\prime}$,
the root vertex $v_{0}\in V(\Gamma^{\prime})$ is chosen to be the vertex which
resulted from contracting $C^{\bullet}$.

Let $m\coloneqq|V(\tau_{0})|-1$. We define $v_{1},\ldots,v_{m}$,
$\mathcal{M}(v_{i})$, $\mathcal{A}_{j}(v_{i})$, $\tau_{i}$, $p_{i}$,
$u_{1}^{i},\ldots,u_{p_{i}}^{i}$, $e_{k}^{i}$, $f_{k}^{i}$, $j_{k}^{i}$,
$\nu_{k}^{i}$, $\Delta(v_{i})$ and $b(i)$ analogously to Step 10 of the proof
of Theorem 8.1. In particular, we again have that

$p_{i}\leq 12D-1$ if $v_{i}$ is an inner tree vertex, and
$\Delta(\tau_{0})\leq 12\cdot 2^{\ell}D$. (9.11)

Step 13: Finding an external skeleton for $\bm{T^{*}}$. We now generate an
external skeleton, following Step 11 of the proof of Theorem 8.1. Using this
external skeleton, we will construct a first skeleton in Step 16 and then
extend it in Step 17 by incorporating the special absorbing structures for the
vertices in $\mathcal{U}$.

Let $\mathcal{M}_{\mathrm{Res}}\subseteq V(\mathcal{Q}^{n})$ be the union of
all the clones of $R^{\prime\prime}$. For each $x\in\mathcal{U}$, consider the
graph $\mathit{CS}(x)_{I}\subseteq I$, and let
$\mathcal{M}_{\mathit{CS}}\subseteq\mathcal{Q}^{n}$ be the union of all the
clones of $\bigcup_{x\in\mathcal{U}}\mathit{CS}(x)_{I}$. We construct an
external skeleton $L^{\bullet}$ which satisfies properties
$(\mathrm{ES}1)$–$(\mathrm{ES}4)$ as in the proof of Theorem 8.1 and the
following variant of $(\mathrm{ES}5)$:

  1. $(\mathrm{ES}5)$

$L^{\bullet}\cap(\mathcal{M}_{\mathrm{Res}}\cup
V(\mathcal{M}_{\mathit{CS}}))=\varnothing$.

The construction of $L^{\bullet}$ is identical to Step 11 of the proof of
Theorem 8.1. The new $(\mathrm{ES}5)$ holds because of the definition of
$\tau_{0}$. Indeed, by $(\mathrm{C^{\prime}}2)$ and $(\mathrm{C^{\prime}}3)$
together with the definition of $R^{\prime\prime}$ and $T^{*}$, observe that
$V(T^{*})\cap(R^{\prime\prime}\cup\bigcup_{x\in\mathcal{U}}V(\mathit{CS}(x)_{I}))=\varnothing$.
Moreover, by construction, all vertices in $L^{\bullet}$ are incident to some
edge in a clone of the tree $T^{*}$, and thus they cannot lie in
$\mathcal{M}_{\mathrm{Res}}\cup V(\mathcal{M}_{\mathit{CS}})$.

Step 14: Constructing an auxiliary tree $\bm{\tau_{0}^{\prime}}$. We now
extend $\tau_{0}$ to a new auxiliary tree $\tau_{0}^{\prime}$ which encodes
information about all cube molecules which intersect $T^{\prime\prime\prime}$.
This is done as in Step 12 of the proof of Theorem 8.1, except that, again,
$\mathcal{C}_{3}^{\prime\prime\prime}$ plays the role of
$\mathcal{C}^{\prime\prime\prime}$ and $T^{\prime\prime\prime}$ plays the role
of $T^{\prime\prime}$. Then, the cubes represented in $\tau_{0}^{\prime}$ are
precisely all those in $\mathcal{C}^{\prime\prime\prime}_{3}$.

Analogously to the proof of Theorem 8.1, it follows from
$(\mathrm{C^{\prime}}1)$ that

$d_{\tau_{0}^{\prime}}(v)\leq 12D$ for all $v\in V(\tau_{0}^{\prime})$ which
are inner tree vertices, and $\Delta(\tau_{0}^{\prime})\leq 12\cdot
2^{\ell}D$. (9.12)

By $(\mathrm{C^{\prime}}5)$$(\mathrm{C^{\prime}}5.3)$ and
$(\mathrm{C^{\prime}}6)$$(\mathrm{C^{\prime}}6.3)$, we have that

  1. $(\mathrm{CP})$

every cube $C$ belonging to some absorbing $\ell$-cube pair in
$\mathcal{C}^{\mathrm{sc}}\cup\mathcal{C}^{\neg\mathrm{sc}}$ is represented in
$\tau_{0}^{\prime}$.

Finally, for each $x\in V(I)$, let $\zeta(x)$ denote the number of vertices
$y\in N_{I}(x)$ which are represented in $\tau_{0}^{\prime}$ by atomic
vertices. By $(\mathrm{C^{\prime}}4)$, we have that

$\zeta(x)\geq(1-2/\ell^{4})n.$ (9.13)

Let $m^{\prime}\coloneqq|V(\tau_{0}^{\prime})|-1$ and label
$V(\tau_{0}^{\prime})\setminus
V(\tau_{0})=\\{v_{m+1},\ldots,v_{m^{\prime}}\\}$ arbitrarily. We define
$\tau_{i}^{\prime}$, $p_{i}^{\prime}$,
$u_{1}^{i},\ldots,u_{p_{i}^{\prime}}^{i}$, $e_{k}^{i}$, $f_{k}^{i}$,
$j_{k}^{i}$, $\nu_{k}^{i}$, $\Delta(v_{i})$, $b(i)$, $\ell_{i}$ and $m_{i}$ as
in Step 12 of the proof of Theorem 8.1.

Step 15: Fixing absorbing $\bm{\ell}$-cube pairs for the vertices that need to
be absorbed. We can now determine every vertex in $V(\mathcal{Q}^{n})$ that
will have to be absorbed via absorbing $\ell$-cube pairs into the almost
spanning cycle we are going to construct. Recall from Step 11 that
$\mathit{SA}^{v}=\bigcup_{y\in\mathcal{U}}V(\mathit{SA}(y))$. For every vertex
$x\in V(I)$ not represented in $\tau_{0}^{\prime}$, we will have to absorb all
vertices in $\mathcal{M}_{x}\setminus\mathit{SA}^{v}$. Furthermore, for each
$v\in V(\tau_{0})$ which is an inner tree vertex, we will also need to absorb
all vertices in $\mathcal{M}_{v}\setminus
L^{\bullet}=\mathcal{M}_{v}\setminus(L^{\bullet}\cup\mathit{SA}^{v})$. (The
fact that $\mathcal{M}_{v}\cap\mathit{SA}^{v}=\varnothing$ follows by
$(\mathrm{C^{\prime}}3)$.) Recall the definition of
$V_{\mathrm{abs}}^{\prime}$ from Step 10. Let $V_{\mathrm{abs}}\subseteq V(I)$
be the set of all vertices which are not represented in $\tau_{0}^{\prime}$ by
an atomic vertex. Therefore, $V_{\mathrm{abs}}$ is the set of all vertices
$x\in V(I)$ such that some clone of $x$ needs to be absorbed. Moreover,
$V_{\mathrm{abs}}=V(I)\setminus\bigcup_{C\in\mathcal{C}^{\prime\prime\prime}_{3}}V(C)$
and, thus, $(\mathrm{C^{\prime}}9)$ and the definition of
$\mathcal{C}_{3}^{\prime\prime\prime}$ at the end of Step 11 imply that
$V_{\mathrm{abs}}\subseteq V_{\mathrm{abs}}^{\prime}$. It follows from (9.13)
that

$|V_{\mathrm{abs}}|\leq 2^{n-s+1}/\ell^{4}.$ (9.14)

Now, for each $x\in V_{\mathrm{abs}}$, we will pair all those vertices in
$\mathcal{M}_{x}$ which need to be absorbed (each pair consisting of one
vertex of each parity) and fix an absorbing $\ell$-cube pair for each such
pair of vertices. Recall that a difference between this pairing and the
pairing in Step 13 of the proof of Theorem 8.1 is that, in Theorem 8.1, we
could guarantee that each pair was contained in one of the slices defined in
Step 3. Since a special absorbing structure might not lie in a single slice,
we now cannot guarantee this anymore. Instead, we can impose that each pair
either lies in a slice or in two consecutive slices (with respect to their
labelling). The absorbing $\ell$-cube pair that we fix for each pair will be
the one given by $(\mathrm{C^{\prime}}5)$ or $(\mathrm{C^{\prime}}6)$,
depending on whether $x\in V_{\mathrm{sc}}$ or not.

For each $x\in V_{\mathrm{abs}}$, let $S(x)\coloneqq
V(\mathcal{M}_{x})\cap(L^{\bullet}\cup\mathit{SA}^{v})=V(\mathcal{M}_{x})\cap(L^{\bullet}\cup
V(\mathcal{M}_{\mathit{CS}}))$. It follows by
$(\mathrm{ES}1)$–$(\mathrm{ES}5)$, $(\mathrm{R}3)$ and the definition of our
special absorbing structures that $|S(x)|\leq 25D$ and $S(x)$ contains the
same number of vertices of each parity. (Here we also use that $p_{i}\leq
12D-1$ for every inner tree vertex $v_{i}$ by (9.11) and (9.12).) Therefore,
the matching $\mathfrak{M}(\mathcal{M}_{x},S(x))$ defined in Step 3 is well
defined, and we can use this matching to define our pairing of the vertices in
$V(\mathcal{M}_{x})\setminus S(x)$. Recall that each edge
$e\in\mathfrak{M}(\mathcal{M}_{x},S(x))$ gives rise to a unique index
$i\in[K]$ via the relation $N(e)=A_{i}(x)$. (Here we ignore all those indices
$i^{\prime}\in[K]$ arising by artificially increasing the size of
$\mathfrak{A}(x)$, see of Step 4 as well as Step 4 in the proof of Theorem
8.1.) For each $x\in V_{\mathrm{abs}}$, let $\mathfrak{I}_{x}\subseteq[K]$ be
the set of indices $i\in[K]$ which correspond to edges in
$\mathfrak{M}(\mathcal{M}_{x},S(x))$.

For each $x\in V_{\mathrm{abs}}$ and $i\in\mathfrak{I}_{x}$, as stated in
$(\mathrm{C^{\prime}}5)$ and $(\mathrm{C^{\prime}}6)$, we have already fixed
an absorbing $\ell$-cube pair for the clones of $x$ corresponding to $(x,i)$.
Let

$V^{\mathrm{abs}}\coloneqq\bigcup_{x\in
V_{\mathrm{abs}}}V(\mathcal{M}_{x})\setminus(L^{\bullet}\cup\mathit{SA}^{v}).$

(Thus, in particular, $V^{\mathrm{abs}}\cap\mathcal{U}=\varnothing$.) As
discussed above, this is the set of all vertices that need to be absorbed via
absorbing $\ell$-cube pairs. Recall that $Q^{\prime}$ was defined before
$(\mathrm{C}1)$–$(\mathrm{C}8)$. It follows from $(\mathrm{C^{\prime}}5)$ and
$(\mathrm{C^{\prime}}6)$ that $((H\cup G)\setminus F)\cup Q^{\prime}$ contains
a set $\mathcal{C}^{\mathrm{abs}}=\\{(C^{l}(u),C^{r}(u)):u\in
V^{\mathrm{abs}}\\}$ of absorbing $\ell$-cube pairs such that
$(\mathrm{C_{1}})$–$(\mathrm{C_{4}})$ in the proof of Theorem 8.1 hold with
$Q^{\prime}$, $\mathcal{C}^{\prime\prime}_{1}$ and
$\mathcal{C}_{1}^{\prime\prime\prime}$ playing the roles of $G^{\prime}$,
$\mathcal{C}^{\prime\prime}$ and $\mathcal{C}^{\prime\prime\prime}$, except
that $(\mathrm{C_{2}})$$({\mathrm{C}_{\mathrm{2.2}}})$ is now replaced by the
following:

  1. $(\mathrm{C_{2.2}})$

if $f_{i}=\\{u_{i},u_{i}^{\prime}\\}$, then there is a vertex $v\in
V_{\mathrm{abs}}$ such that $u_{i}$ and $u_{i}^{\prime}$ are clones of $v$
which lie in either the same or consecutive slices of $\mathcal{M}_{v}$, and
$(C^{l}(u_{i}),C^{r}(u_{i}))$ and
$(C^{l}(u_{i}^{\prime}),C^{r}(u_{i}^{\prime}))$ are clones of the same
absorbing $\ell$-cube pair for $v$ in $I$ such that
$(C^{l}(u_{i}),C^{r}(u_{i}))$ lies in the same layer as $u_{i}$ and
$(C^{l}(u_{i}^{\prime}),C^{r}(u_{i}^{\prime}))$ lies in the same layer as
$u_{i}^{\prime}$.

We denote by $\mathfrak{L}$, $\mathfrak{R}_{1}$ and $\mathfrak{R}_{2}$ the
collections of all left absorber tips, right absorber tips, and third absorber
vertices, respectively, of the absorbing $\ell$-cube pairs in
$\mathcal{C}^{\mathrm{abs}}$. Observe that by
$(\mathrm{C_{1}})$–$(\mathrm{C_{3}})$ the following properties are satisfied:

  1. $(\mathrm{C}^{enumi}1)$

For all $i\in[m^{\prime}]_{0}$ such that $v_{i}$ is an atomic vertex, we have
that $|\mathfrak{L}\cap V(\mathcal{M}(v_{i}))|\in\\{0,2\\}$. If
$|\mathfrak{L}\cap V(\mathcal{M}(v_{i}))|=2$, then these two vertices
$u,u^{\prime}$ lie in different atoms of either the same or consecutive slices
of $\mathcal{M}(v_{i})$, and satisfy that $u\neq_{\mathrm{p}}u^{\prime}$.

  2. $(\mathrm{C}^{enumi}2)$

For all $i\in[m^{\prime}]_{0}$ such that $v_{i}$ is an atomic vertex, we have
that $|(\mathfrak{R}_{1}\cup\mathfrak{R}_{2})\cap
V(\mathcal{M}(v_{i}))|\in\\{0,4\\}$. If
$|(\mathfrak{R}_{1}\cup\mathfrak{R}_{2})\cap V(\mathcal{M}(v_{i}))|=4$, then
these four vertices form two pairs such that one vertex of each pair belongs
to $\mathfrak{R}_{1}$ and the other to $\mathfrak{R}_{2}$. Each of these pairs
lies in a different atom of the same or consecutive slices of
$\mathcal{M}(v_{i})$ and satisfies that its two vertices are adjacent in
$Q^{\prime}$.

  3. $(\mathrm{C}^{enumi}3)$

For all $i\in[m^{\prime}]_{0}$ such that $v_{i}$ is an atomic vertex, if
$\mathfrak{L}\cap V(\mathcal{M}(v_{i}))\neq\varnothing$, then
$(\mathfrak{R}_{1}\cup\mathfrak{R}_{2})\cap
V(\mathcal{M}(v_{i}))=\varnothing$.

  4. $(\mathrm{C}^{enumi}4)$

The sets described in $(\mathrm{C}^{enumi}1)$ and $(\mathrm{C}^{enumi}2)$
partition $\mathfrak{L}$ and $\mathfrak{R}_{1}\cup\mathfrak{R}_{2}$,
respectively.

Indeed, $(\mathrm{C}^{enumi}1)$–$(\mathrm{C}^{enumi}3)$ follow from
$(\mathrm{C_{1}})$–$(\mathrm{C_{3}})$, and $(\mathrm{C}^{enumi}4)$ follows by
$(\mathrm{CP})$.

For each $u\in V^{\mathrm{abs}}$, we denote the edge consisting of the right
absorber tip and the third absorber vertex of $(C^{l}(u),C^{r}(u))$ by
$e_{\mathrm{abs}}(u)$, and we denote by $\mathcal{P}^{\mathrm{abs}}(u)$ the
path of length three formed by the third absorber vertex, the left absorber
tip, $u$, and the right absorber tip, visited in this order. Note that
$e_{\mathrm{abs}}(u)\in E(Q^{\prime})$ by $(\mathrm{C_{1}})$. Moreover, recall
that $\mathcal{C}^{\mathrm{abs}}$ consists of absorbing $\ell$-cube pairs in
$((H\cup G)\setminus F)\cup Q^{\prime})$. Thus,
$\mathcal{P}^{\mathrm{abs}}(u)\subseteq((H\cup G)\setminus F)\cup Q^{\prime}$.

Step 16: Constructing the skeleton. As in Step 14 of the proof of Theorem 8.1,
we now define the skeleton $\mathcal{L}=(x_{1},\ldots,x_{r})$ for the almost
spanning cycle. We again let
$\mathcal{L}^{\bullet}\coloneqq\\{x_{1},\ldots,x_{r}\\}$. The skeleton
$\mathcal{L}$ again satisfies $(\mathrm{S}1)$–$(\mathrm{S}7)$ in the proof of
Theorem 8.1, except that $Q^{\prime}$ now plays the role of $G^{\prime}$ and,
$(\mathrm{S}3)$ and $(\mathrm{S}7)$ are now replaced by the following.

  1. $(\mathrm{S}3)$

For every $k\in[r-1]$, if $x_{k}$ and $x_{k+1}$ do not both lie in the same
slice of a cube molecule represented in $\tau_{0}^{\prime}$, then
$\\{x_{k},x_{k+1}\\}\in E(Q^{\prime})$. Moreover, in this case, if $x_{k+1}$
lies in a cube molecule represented in $\tau_{0}^{\prime}$, then $x_{k+2}$
lies in the same slice of this cube molecule as $x_{k+1}$.

  2. $(\mathrm{S}7)$

$\mathcal{L}^{\bullet}\cap(\mathfrak{L}\cup\mathfrak{R}_{1}\cup
V^{\mathrm{abs}}\cup V(\mathcal{M}_{\mathit{CS}}))=\varnothing$ and
$L^{\bullet}\subseteq\mathcal{L}^{\bullet}$.

The construction of $\mathcal{L}$ is identical to that in Theorem 8.1. The
only difference is that the ‘forbidden set $\mathcal{F}$’ which the skeleton
has to avoid is replaced by
$\mathcal{F}\coloneqq\mathfrak{L}\cup\mathfrak{R}_{1}\cup L^{\bullet}\cup
V(\mathcal{M}_{\mathit{CS}})$ (this is required to ensure that $(\mathrm{S}7)$
holds). For each $i\in[m^{\prime}]_{0}$ such that $v_{i}$ is an atomic vertex
and each $j\in[t]$, let
$\mathfrak{J}_{i,j}\coloneqq\\{k\in[r]:x_{k},x_{k+1}\in
V(\mathcal{M}_{j}(v_{i}))\\}$ and
$S_{i,j}\coloneqq\\{\\{x_{k},x_{k+1}\\}:k\in\mathfrak{J}_{i,j}\\}$.

Step 17. Incorporating special absorbing structures into the skeleton. In this
step, we are going to incorporate all special absorbing structures fixed in
Step 11 into the skeleton we just constructed. Note that all cube molecules
referred to are represented by atomic vertices in $\tau^{\prime}_{0}$, and all
slices referred to are one of the $t$ slices of each of these molecules
defined in Step 3. For each $x\in\mathcal{U}$, consider the consistent system
of paths $\mathit{CS}(x)$ and the special absorbing structure $\mathit{SA}(x)$
given by $(\mathrm{C^{\prime}}7)$. By $(\mathrm{S}7)$, we have that
$\mathcal{L}$ avoids $\mathit{CS}(x)$. Moreover, by the definition of
$\mathcal{C}^{\prime\prime\prime}_{3}$ at the end of Step 11, each
$C^{\prime}\in\mathbf{C}(\mathit{SA}(x))$ is a clone of some
$C\in\mathcal{C}^{\prime\prime\prime}_{3}$. Thus, by $(\mathrm{S}5)$ we have
that $\mathcal{L}$ has positive intersection with each slice which contains a
vertex of $\mathrm{end}(\mathit{CS}(x))$.

Recall that a special absorbing structure is a tuple of paths and cubes (see
Section 9.1). For each $z\in\mathcal{U}$, let $P^{z}_{1}$ denote the first
path of $\mathit{SA}(z)$. Let $x(z)\in\mathcal{L}^{\bullet}$ be the first
vertex in $\mathcal{L}$ that is contained in the slice which contains the
first vertex of $P^{z}_{1}$. Let $x^{\prime}(z)$ be the successor of $x(z)$ in
$\mathcal{L}$ (in particular, by $(\mathrm{S}3)$, both $x(z)$ and
$x^{\prime}(z)$ lie in the same slice). Now, for each $z\in\mathcal{U}$,
depending on the type of the special absorbing structure $\mathit{SA}(z)$, we
will update $\mathcal{L}$ in different ways.

  1. (I)

If $\mathit{SA}(z)$ is a special absorbing structure of Type I, proceed as
follows. Let $P^{z}_{1},\dots,P^{z}_{6}$ be the six paths of $\mathit{SA}(z)$.
Let $S\coloneqq\bigtimes_{i=1}^{6}P^{z}_{i}$ and let $S^{-1}$ denote the same
sequence of vertices in reverse order. If $x(z)$ has opposite parity to the
initial vertex of $P^{z}_{1}$, then we replace the segment
$(x(z),x^{\prime}(z))$ of $\mathcal{L}$ by $(x(z),S,x^{\prime}(z))$;
otherwise, we we replace the segment $(x(z),x^{\prime}(z))$ by
$(x(z),S^{-1},x^{\prime}(z))$.

  2. (II)

If $\mathit{SA}(z)$ is a special absorbing structure of Type II, we proceed as
follows. Let $P^{z}_{1}$ and $P^{z}_{2}$ be the two paths of $\mathit{SA}(z)$.
Let $y^{1}$ and $x^{1}_{0}$ be the first and last vertices of $P^{z}_{1}$, and
let $y^{2}$ and $x^{2}_{0}$ be the first and last vertices of $P^{z}_{2}$,
respectively. Let $v,v^{\prime}\in V(\tau_{0}^{\prime})$ and
$t_{1},t_{2},t_{3}\in[t]$ be such that $y^{1}\in V(\mathcal{M}_{t_{1}}(v))$,
$x^{1}_{0}\in V(\mathcal{M}_{t_{2}}(v^{\prime}))$, and $y^{2}\in
V(\mathcal{M}_{t_{3}}(v^{\prime}))$ (this implies $x_{0}^{2}\in
V(\mathcal{M}_{t_{3}}(v))$).

We now define two sequences of vertices $S^{z}_{1}$ and $S^{z}_{2}$ following
similar ideas to Step 16. Recall that, for each $i\in[2^{s}]$, we use
$\hat{e}_{i}$ to denote the direction of the edges between $L_{i}$ and
$L_{i+1}$. If $t_{3}\geq t_{2}$, let $m_{1}\coloneqq t_{3}-t_{2}$; otherwise,
let $m_{1}\coloneqq t-(t_{2}-t_{3})$. For each $k\in[m_{1}-1]_{0}$,
iteratively choose a vertex $y^{1}_{k}\in
V(\mathcal{A}_{(t_{2}+k)q}(v^{\prime}))\setminus\mathcal{L}^{\bullet}$
satisfying that

    1. $1$.

$y_{k}^{1}\neq_{\mathrm{p}}x_{k}^{1}$;

    2. $2$.

$x_{k+1}^{1}\coloneqq
y_{k}^{1}+\hat{e}_{(t_{2}+k)q}\notin\mathcal{L}^{\bullet}$, and

    3. $3$.

$\\{y_{k}^{1},x_{k+1}^{1}\\}\in E(Q^{\prime})$.

We set $S^{z}_{1}\coloneqq\bigtimes_{k=0}^{m_{1}-1}(y_{k}^{1},x_{k+1}^{1})$.

In order to construct $S_{2}^{z}$, we proceed similarly. If $t_{3}\geq t_{1}$,
let $m_{2}\coloneqq t_{3}-t_{1}$; otherwise, let $m_{2}\coloneqq
t-(t_{1}-t_{3})$. For each $k\in[m_{2}-1]_{0}$, iteratively choose a vertex
$y^{2}_{k}\in
V(\mathcal{A}_{(t_{3}-k-1)q+1}(v))\setminus\mathcal{L}^{\bullet}$ satisfying
that

    1. $1$.

$y_{k}^{2}\neq_{\mathrm{p}}x_{k}^{2}$;

    2. $2$.

$x_{k+1}^{2}\coloneqq
y_{k}^{2}+\hat{e}_{(t_{3}-k-1)q}\notin\mathcal{L}^{\bullet}$, and

    3. $3$.

$\\{y_{k}^{2},x_{k+1}^{2}\\}\in E(Q^{\prime})$.

Now, let $S^{z}_{2}\coloneqq\bigtimes_{k=0}^{m_{2}-1}(y_{k}^{2},x_{k+1}^{2})$.

Let $S\coloneqq P^{z}_{1}\times S^{z}_{1}\times P^{z}_{2}\times S^{z}_{2}$,
and let $S^{-1}$ denote the same sequence of vertices in reverse order.
Finally, we replace the segment $(x(z),x^{\prime}(z))$ of $\mathcal{L}$ by
$(x(z),S,x^{\prime}(z))$ if $x(z)$ has parity opposite to the initial vertex
of $P^{z}_{1}$; otherwise, we replace $(x(z),x^{\prime}(z))$ by
$(x(z),S^{-1},x^{\prime}(z))$.

  3. (III)

If $\mathit{SA}(z)$ is a special absorbing structure of Type III, we proceed
as follows. Let $P^{z}_{1}$, $P^{z}_{2}$ and $P^{z}_{3}$ be the three paths of
$\mathit{SA}(z)$. For each $i\in[3]$, let $y^{i}$ and $x_{0}^{i}$ be the first
and last vertices of $P^{z}_{i}$, respectively. Let $v_{1},v_{2},v_{3}\in
V(\tau_{0}^{\prime})$ and $t_{1},t_{2}\in[t]$ be such that $y^{1}\in
V(\mathcal{M}_{t_{1}}(v_{1}))$, $y^{2}\in V(\mathcal{M}_{t_{1}}(v_{2}))$ and
$y^{3}\in V(\mathcal{M}_{t_{2}}(v_{3}))$ (note this implies that $x^{1}_{0}\in
V(\mathcal{M}_{t_{2}}(v_{2}))$, $x^{2}_{0}\in V(\mathcal{M}_{t_{1}}(v_{3}))$
and $x^{3}_{0}\in V(\mathcal{M}_{t_{2}}(v_{1}))$).

For each $i\in[3]$, we define a sequence $S^{z}_{i}$ as follows. If $t_{2}\geq
t_{1}$, let $m^{*}\coloneqq t_{2}-t_{1}$; otherwise, let $m^{*}\coloneqq
t-(t_{1}-t_{2})$. For each $k\in[m^{*}-1]_{0}$, iteratively choose three
vertices $y^{1}_{k}\in
V(\mathcal{A}_{(t_{2}-k-1)q+1}(v_{2}))\setminus\mathcal{L}^{\bullet}$,
$y^{2}_{k}\in
V(\mathcal{A}_{(t_{1}+k)q}(v_{3}))\setminus\mathcal{L}^{\bullet}$ and
$y^{3}_{k}\in
V(\mathcal{A}_{(t_{2}-k-1)q+1}(v_{1}))\setminus\mathcal{L}^{\bullet}$
satisfying that

    1. $1$.

$y_{k}^{i}\neq_{\mathrm{p}}x_{k}^{i}$ for all $i\in[3]$;

    2. $2$.

$x_{k+1}^{1}\coloneqq
y_{k}^{1}+\hat{e}_{(t_{2}-k-1)q}\notin\mathcal{L}^{\bullet}$,
$x_{k+1}^{2}\coloneqq
y_{k}^{2}+\hat{e}_{(t_{1}+k)q}\notin\mathcal{L}^{\bullet}$ and
$x_{k+1}^{3}\coloneqq
y_{k}^{3}+\hat{e}_{(t_{2}-k-1)q}\notin\mathcal{L}^{\bullet}$, and

    3. $3$.

$\\{y_{k}^{i},x_{k+1}^{i}\\}\in E(Q^{\prime})$ for all $i\in[3]$.

Then, for each $i\in[3]$, we define
$S^{z}_{i}\coloneqq\bigtimes_{k=0}^{m^{*}-1}(y_{k}^{i},x_{k+1}^{i})$.

Let $S\coloneqq\bigtimes_{i=1}^{3}(P^{z}_{i}\times S^{z}_{i})$, and let
$S^{-1}$ denote the same sequence in reverse order. Finally, we replace the
segment $(x(z),x^{\prime}(z))$ of $\mathcal{L}$ by $(x(z),S,x^{\prime}(z))$ if
$x(z)$ has parity opposite to the initial vertex of $P^{z}_{1}$; otherwise, we
replace $(x(z),x^{\prime}(z))$ by $(x(z),S^{-1},x^{\prime}(z))$.

Write $\mathcal{L}=(x_{1},\ldots,x_{r})$, for some $r\in\mathbb{N}$, for the
extended skeleton into which all the special absorbing structures
$\mathit{SA}(z)$ for $z\in\mathcal{U}$ have been incorporated, and let
$\mathcal{L}^{\bullet}\coloneqq\\{x_{1},\ldots,x_{r}\\}$. It follows from
$(\mathrm{S}1)$–$(\mathrm{S}7)$ and the construction above (together with the
choice of $v_{0}$ in Step 12) that the following properties hold:

  1. $(\mathrm{S^{\prime}}1)$

For all distinct $k,k^{\prime}\in[r]$, we have that $x_{k}\neq
x_{k^{\prime}}$.

  2. $(\mathrm{S^{\prime}}2)$

$\\{x_{1},x_{r}\\}\in E(Q^{\prime})$.

  3. $(\mathrm{S^{\prime}}3)$

For every $k\in[r-1]$, if $x_{k}$ and $x_{k+1}$ do not both lie in the same
slice of a cube molecule represented in $\tau_{0}^{\prime}$, then
$\\{x_{k},x_{k+1}\\}\in E((H\setminus F)\cup H^{\prime}\cup Q^{\prime})$.
Moreover, in this case $\\{x_{k},x_{k+1}\\}\in E(Q^{\prime})$ unless both
$x_{k}$ and $x_{k+1}$ lie in $\mathit{SA}^{v}$.

  4. $(\mathrm{S^{\prime}}4)$

For every $i\in[m^{\prime}]_{0}$ and every $j\in[t]$, no three consecutive
vertices of $\mathcal{L}$ lie in $\mathcal{M}_{j}(v_{i})$ (here $\mathcal{L}$
is viewed as a cyclic sequence of vertices).

  5. $(\mathrm{S^{\prime}}5)$

For every $i\in[m^{\prime}]$ such that $v_{i}$ is an atomic vertex and every
$j\in[t]$, we have that $|V(\mathcal{M}_{j}(v_{i}))\cap\mathcal{L}^{\bullet}|$
is even and $4\leq|V(\mathcal{M}_{j}(v_{i}))\cap\mathcal{L}^{\bullet}|\leq
14$. Moreover, $|V(\mathcal{M}_{t}(v_{0}))\cap\mathcal{L}^{\bullet}|=4$.

  6. $(\mathrm{S^{\prime}}6)$

For all $k\in[r]$ except two values, we have that
$x_{k}\neq_{\mathrm{p}}x_{k+1}$. The remaining two values $k_{1},k_{2}\in[r]$
correspond to two pairs of vertices
$x_{k_{1}},x_{k_{1}+1},x_{k_{2}},x_{k_{2}+1}\in V(\mathcal{M}_{t}(v_{0}))$.
For these two values, we have that $x_{k_{1}}\neq_{\mathrm{p}}x_{k_{2}}$ and
either

    1. $(\mathrm{i})$

$x_{k_{1}}=_{\mathrm{p}}x_{k_{1}+1}$ and $x_{k_{2}}=_{\mathrm{p}}x_{k_{2}+1}$,
or

    2. $(\mathrm{ii})$

$x_{k_{1}}\neq_{\mathrm{p}}x_{k_{1}+1}$ and
$x_{k_{2}}\neq_{\mathrm{p}}x_{k_{2}+1}$,

where $x_{k_{1}},x_{k_{2}}\in V(\mathcal{A}_{(t-1)q+1}(v_{0}))$ and
$x_{k_{1}+1},x_{k_{2}+1}\in V(\mathcal{A}_{tq}(v_{0}))$.

  7. $(\mathrm{S^{\prime}}7)$

$\mathcal{L}^{\bullet}\cap(\mathfrak{L}\cup\mathfrak{R}_{1}\cup
V^{\mathrm{abs}})=\varnothing$ and
$L^{\bullet}\subseteq\mathcal{L}^{\bullet}$.

Indeed, for $(\mathrm{S^{\prime}}3)$–$(\mathrm{S^{\prime}}6)$ we make use of
the properties of the paths $P_{j}^{z}$ defined in Section 9.1 as well as (AS)
(see Section 9.1) and $(\mathrm{C^{\prime}}7)$. We also use that the set of
all cube molecules represented in $\tau^{\prime}_{0}$ is precisely
$\mathcal{C}^{\prime\prime\prime}_{3}=C^{\prime\prime\prime}_{1}\mathbin{\dot{\cup}}\mathcal{C}^{\prime}_{2}$.
Recall that, by the definition of $\mathcal{C}^{\prime\prime\prime}_{1}$, for
each $C\in\mathcal{C}^{\prime\prime\prime}_{1}$ we have
$V(\mathcal{M}_{C})\cap\mathit{SA}^{v}=\varnothing$. Moreover, by
$(\mathrm{R}3)$ and (AS), for each $C\in\mathcal{C}^{\prime}_{2}$ we have
$|V(\mathcal{M}_{C})\cap\mathit{SA}^{v}|=2$, and these two vertices
$x_{C}^{1},x_{C}^{2}\in V(\mathcal{M}_{C})\cap\mathit{SA}^{v}$ satisfy the
following properties:

  1. (i)

there is some $z\in\mathcal{U}$ and two consecutive paths $P^{z}_{i}$,
$P^{z}_{i+1}$ in $\mathit{SA}(z)$ (with indices taken cyclically) such that
$x_{C}^{1}$ is the final vertex of $P^{z}_{i}$ and $x_{C}^{2}$ is the first
vertex of $P^{z}_{i+1}$, and

  2. (ii)

$\mathbf{C}(\mathit{SA}(z))$ contains two clones $C_{1},C_{2}$ of $C$, where
$x^{1}_{C}\in V(C_{1})$ and $x_{C}^{2}\in V(C_{2})$.

Moreover, to check $(\mathrm{S^{\prime}}5)$ for case (I), note that the
definition of $f$ in a consistent system of paths of Type I in Section 9.1
implies that, for each $i\in[6]$, the final vertex of $P^{z}_{i}$ and the
first vertex of $P^{z}_{i+1}$ lie in the same slice.

Step 18: Constructing an almost spanning cycle. Similarly to Step 15 in the
proof of Theorem 8.1, we will now apply the connecting lemmas to obtain an
almost spanning cycle in $(H\setminus F)\cup H^{\prime}\cup Q^{\prime}$ from
$\mathcal{L}=(x_{1},\ldots,x_{r})$. For each $i\in[m^{\prime}]$ such that
$v_{i}$ is an atomic vertex, by $(\mathrm{C}^{enumi}1)$ there is at most one
value $k(i)\in[t]$ such that $|\mathfrak{L}\cap
V(\mathcal{M}_{k(i)}(v_{i}))|=1$ and $|\mathfrak{L}\cap
V(\mathcal{M}_{k(i)+1}(v_{i}))|=1$. If such $k(i)$ exists, then we denote by
$k^{*}(i)$ an additional index not in $[t]$ and let
$\mathfrak{J}_{i,k^{*}(i)}\coloneqq\mathfrak{J}_{i,k(i)}\cup\mathfrak{J}_{i,k(i)+1}$,
$S_{i,k^{*}(i)}\coloneqq S_{i,k(i)}\cup S_{i,k(i)+1}$ and
$\mathcal{M}_{k^{*}(i)}(v_{i})\coloneqq\mathcal{M}_{k(i)}(v_{i})\cup\mathcal{M}_{k(i)+1}(v_{i})$.
Let

$\mathfrak{T}(i)\coloneqq\begin{cases}[t]&\text{if there is no }k(i)\text{ as
above,}\\\
([t]\cup\\{k^{*}(i)\\})\setminus\\{k(i),k(i)+1\\}&\text{otherwise.}\end{cases}$

Observe that the definition of $v_{0}$ in Step 12 together with
$(\mathrm{C^{\prime}}8)$ ensures that $\mathfrak{T}(0)=[t]$.

For each $i\in[m^{\prime}]_{0}$ such that $v_{i}$ is an atomic vertex and for
each $j\in\mathfrak{T}(i)$, except the pair $(0,t)$, we apply Lemma 8.8 to
$\mathcal{M}_{j}(v_{i})$ and the graph $Q^{\prime}$, with $\mathfrak{L}\cap
V(\mathcal{M}_{j}(v_{i}))$, $(\mathfrak{R}_{1}\cup\mathfrak{R}_{2})\cap
V(\mathcal{M}_{j}(v_{i}))$ and $S_{i,j}$ playing the roles of $L$, $R$ and the
pairs of vertices described in Lemma 8.8$(\mathrm{C}3)$, respectively. For
$\mathcal{M}_{t}(v_{0})$, we apply Lemma 8.8 or Lemma 8.9 depending on whether
$(\mathrm{S^{\prime}}6)$$(\mathrm{ii})$ or
$(\mathrm{S^{\prime}}6)$$(\mathrm{i})$ holds in $(\mathrm{S^{\prime}}6)$. For
each $i\in[m^{\prime}]_{0}$ such that $v_{i}$ is an atomic vertex and each
$j\in\mathfrak{T}(i)$, this yields $|\mathfrak{J}_{i,j}|$ vertex-disjoint
paths $(\mathcal{P}^{i,j}_{k})_{k\in\mathfrak{J}_{i,j}}$ in
$\mathcal{M}_{j}(v_{i})\cup Q^{\prime}=Q^{\prime}$ such that, for each
$k\in\mathfrak{J}_{i,j}$, properties $(\mathrm{i})$–$(\mathrm{iii})$ in Step
15 of the proof of Theorem 8.1 hold.

Now consider the path obtained as follows by going through $\mathcal{L}$.
Start with $x_{1}$. For each $k\in[r]$, if there exist $i\in[m^{\prime}]_{0}$
and $j\in\mathfrak{T}(i)$ such that $\\{x_{k},x_{k+1}\\}\in S_{i,j}$, add
$\mathcal{P}^{i,j}_{k}$ to the path; otherwise, add the edge
$\\{x_{k},x_{k+1}\\}$ (this must be an edge of $(H\setminus F)\cup
H^{\prime}\cup Q^{\prime}$ by $(\mathrm{S^{\prime}}3)$). Finally, add the edge
$\\{x_{r},x_{1}\\}$ of $Q^{\prime}$ (this is given by
$(\mathrm{S^{\prime}}2)$) to the path to close it into a cycle $\mathfrak{H}$
in $(H\setminus F)\cup H^{\prime}\cup Q^{\prime}$. This cycle $\mathfrak{H}$
satisfies $(\mathrm{HC}1)$–$(\mathrm{HC}3)$ as in the proof of Theorem 8.1 as
well as the following:

  1. $(\mathrm{HC}4)$

For all $x\in\mathcal{U}$, we have that $\\{x,x+a(x)\\},\\{x,x+b(x)\\}\in
E(\mathfrak{H})$.

  2. $(\mathrm{HC}5)$

For all $x\in V(\mathfrak{H})\setminus\mathit{SA}^{v}$, each of the two edges
of $\mathfrak{H}$ incident to $x$ lies in $Q^{\prime}$.

Indeed, $(\mathrm{HC}4)$ follows immediately by the definition of $P_{1}$ in
each of the three types of special absorbing structures defined in Section
9.1, and $(\mathrm{HC}5)$ follows from $(\mathrm{S^{\prime}}3)$.

Step 19: Absorbing vertices to form a Hamilton cycle. Similarly as in Step 16
of the proof of Theorem 8.1, for each $u\in V^{\mathrm{abs}}$ we now replace
the edge $e_{\mathrm{abs}}(u)$ by the path $\mathcal{P}_{\mathrm{abs}}(u)$
(recall from the end of Step 15 that $\mathcal{P}_{\mathrm{abs}}(u)$ lies in
$((H\cup G)\setminus F)\cup Q^{\prime}$). Clearly, this incorporates all
vertices of $\mathfrak{L}\cup V^{\mathrm{abs}}$ into the cycle and, by
$(\mathrm{HC}2)$ and $(\mathrm{HC}3)$, the resulting cycle
$\mathfrak{H}^{\prime}$ is Hamiltonian. Moreover, since by $(\mathrm{C_{3}})$
the endvertices of each edge $e_{\mathrm{abs}}(u)$ lie in cubes belonging to
$\mathcal{C}^{\prime\prime\prime}_{1}$, all these endvertices avoid
$\mathcal{U}$. Thus, by $(\mathrm{HC}4)$, for each $x\in\mathcal{U}$ the edges
at $x$ in $\mathfrak{H}^{\prime}$ are still $\\{x,x+a(x)\\}$ and
$\\{x,x+b(x)\\}$, and so, in particular, by $(\mathrm{C^{\prime}}7)$ these
edges belong to $H^{\prime}$.

It now remains to show that $\mathfrak{H}^{\prime}$ is
$(\mathcal{U},\ell^{2},s)$-good. Fix any vertex $x\in\mathcal{U}$. Let
$Y_{x}\coloneqq N_{\mathcal{Q}^{n}}(x)\setminus(V(\mathit{SA}(x))\cup
V^{\mathrm{abs}})$ (that is, by $(\mathrm{C^{\prime}}3)$, $Y_{x}$ is the set
of all vertices in
$N_{\mathcal{Q}^{n}}(x)\setminus\mathit{SA}^{v}=N_{\mathcal{Q}^{n}}(x)\setminus
V(\mathit{SA}(x))$ which lie in clones of cubes which are represented in
$\tau_{0}^{\prime}$ by atomic vertices). By (9.13), we have that
$|Y_{x}|\geq(1-2/\ell^{4})n-|V(\mathit{SA}(x))|\geq(1-1/\ell^{3})n$.
9.3$(\mathrm{ii})$ implies that
$Y_{x}\cap(\mathfrak{L}\cup\mathfrak{R}_{1}\cup\mathfrak{R}_{2})=\varnothing$,
so by definition we have that $Y_{x}\cap\bigcup_{u\in
V^{\mathrm{abs}}}V(\mathcal{P}_{\mathrm{abs}}(u))=\varnothing$. It then
follows by $(\mathrm{HC}5)$ that, for each $y\in Y_{x}$, each of the two edges
of $\mathfrak{H}^{\prime}$ incident to $y$ lies in $Q^{\prime}$. But
$Q^{\prime}$ is $(\mathcal{U},2\ell^{2},s)$-good by 9.4. Now, even if all the
edges incident to the remaining vertices $y\in N_{\mathcal{Q}^{n}}(x)\setminus
Y_{x}$ used the same pair of directions, it follows that the edges of
$\mathfrak{H}^{\prime}$ incident to the vertices in $N_{\mathcal{Q}^{n}}(x)$
use each direction of $\mathcal{Q}^{n}$ which is not an $s$-direction at most
$n/\ell^{3}+n/(2\ell^{2})\leq n/\ell^{2}$ times. ∎

###  9.4. Proofs of Theorem 1.8 and Theorem 1.5

We now deduce Theorems 1.8 and 1.5 from Theorem 9.6.

###### Proof of Theorem 1.8.

Let $0<1/n\ll
1/\ell\ll\varepsilon_{1}\ll\varepsilon\ll\varepsilon_{2}\ll\gamma\ll 1/k\leq
1$. Let $s\coloneqq 10\ell$. Let $H^{*}\sim\mathcal{Q}^{n}_{1/2-2\varepsilon}$
and $Q\sim\mathcal{Q}^{n}_{\varepsilon}$. Observe that $H^{*}\cup
Q\sim\mathcal{Q}^{n}_{1/2-\varepsilon^{\prime}}$ for some
$\varepsilon^{\prime}\geq\varepsilon$, so it suffices to prove that $H\cup
H^{*}\cup Q$ contains the desired Hamilton cycles and perfect matchings.

By Lemma 9.4 with $2\varepsilon$ playing the role of $\varepsilon$, we have
that a.a.s. $H^{*}$ is
$(s,\ell,\varepsilon_{1},\varepsilon_{2},\gamma,\mathcal{U}(H^{*},\varepsilon_{1}))$-robust.
Condition on this event and let
$\mathcal{U}\coloneqq\mathcal{U}(H^{*},\varepsilon_{1})$. By an application of
Lemma 9.4(ii), it follows that there exists a decomposition of $H^{*}$ into
$r\coloneqq\lceil k/2\rceil$ edge-disjoint spanning subgraphs
$H^{*}_{1},\ldots,H^{*}_{r}$ such that, for every $i\in[r]$, we have that
$H^{*}_{i}$ is
$(s,\ell,\varepsilon_{1}/(2r),\varepsilon_{2},\gamma/r^{10}),\mathcal{U})$-robust.

Consider a random decomposition of $Q$ into $r$ edge-disjoint spanning
subgraphs $Q_{1},\ldots,Q_{r}$ in such a way that, if $e\in Q$, then $e$ is
assigned to one of the $Q_{i}$ chosen uniformly at random and independently of
all other edges. It follows that, for all $i\in[r]$, we have
$Q_{i}\sim\mathcal{Q}^{n}_{\varepsilon/r}$.

Let $\Phi$ be a constant such that Theorem 9.6 holds with
$\varepsilon_{1}/(2r)$, $\gamma/r^{10}$, $\varepsilon/r$ and $r+2$ playing the
roles of $\varepsilon_{1}$, $\gamma$, $\eta$ and $c$, respectively. (In
particular, $\Phi\geq r$.) For each $i\in[r]$, apply Theorem 9.6 with
$H_{i}^{*}$, $Q_{i}$, $\varepsilon_{1}/(2r)$, $\gamma/r^{10}$, $\varepsilon/r$
and $r+2$ playing the roles of $H$, $Q$, $\varepsilon_{1}$, $\gamma$, $\eta$
and $c$, respectively, to conclude that a.a.s. there is a
$(\mathcal{U},\ell^{2},s)$-good subgraph $Q_{i}^{\prime}\subseteq Q_{i}$ with
$\Delta(Q_{i}^{\prime})\leq\Phi$ such that, for every
$H^{\prime}\subseteq\mathcal{Q}^{n}$ such that $d_{H^{\prime}}(x)\geq 2$ for
every $x\in\mathcal{U}$, and every $F\subseteq\mathcal{Q}^{n}$ with
$\Delta(F)\leq(r+2)\Phi$ which is $(\mathcal{U},\ell,s)$-good, we have that
$((H^{*}_{i}\cup Q_{i})\setminus F)\cup H^{\prime}\cup Q_{i}^{\prime}$
contains a $(\mathcal{U},\ell^{2},s)$-good Hamilton cycle $C$ such that, for
all $x\in\mathcal{U}$, both edges of $C$ incident to $x$ belong to
$H^{\prime}$. Condition on the event that this holds for all $i\in[r]$ (which
holds a.a.s. by a union bound).

Now consider the graph $H$ from the statement of Theorem 1.8. By
$(\mathrm{R}3)$ in Definition 9.3, we can greedily find $r$ edge-disjoint
subgraphs $H_{1},\ldots,H_{r}\subseteq H$ such that

  1. (i)

for each $i\in[\lfloor k/2\rfloor]$, we have that $|E(H_{i})|=2|\mathcal{U}|$
and $d_{H_{i}}(x)=2$ for every $x\in\mathcal{U}$, and

  2. (ii)

if $2r=k+1$, then $H_{r}$ is a matching of size $|\mathcal{U}|$ such that
$d_{H_{r}}(x)=1$ for all $x\in\mathcal{U}$.

Suppose first that $2r=k$. We are going to find $r$ edge-disjoint
$(\mathcal{U},\ell^{2},s)$-good Hamilton cycles $C_{1},\ldots,C_{r}$ with
$H_{i}\subseteq C_{i}$ iteratively. Suppose that for some $i\in[r]$ we have
already found $C_{1},\ldots,C_{i-1}$. Let
$F_{i}\coloneqq\bigcup_{j=1}^{r}Q_{j}^{\prime}\cup\bigcup_{j=1}^{i-1}C_{j}$.
It follows by construction that $F_{i}$ is $(\mathcal{U},\ell,s)$-good and
$\Delta(F_{i})\leq r(\Phi+2)\leq(r+2)\Phi$. Then, by the conditioning above,
the graph $((H_{i}^{*}\cup Q_{i})\setminus F_{i})\cup H_{i}\cup
Q_{i}^{\prime}$ must contain a $(\mathcal{U},\ell^{2},s)$-good Hamilton cycle
$C_{i}$ such that, for each $u\in\mathcal{U}$, both edges of $C_{i}$ incident
to $x$ belong to $H_{i}$. In particular, $H_{i}\subseteq C_{i}$. Take one such
cycle and proceed.

In order to see that these $r$ cycles are pairwise edge-disjoint, suppose that
there exist $i,j\in[r]$ with $i<j$ such that $E(C_{i})\cap
E(C_{j})\neq\varnothing$, and let $e\in E(C_{i})\cap E(C_{j})$. Observe that
$e\notin E(H_{i})\cup E(H_{j})$ because, otherwise, we would have $e$ incident
to some vertex $x\in\mathcal{U}$, and we know that both edges incident to $x$
in $C_{i}$ and $C_{j}$ belong to $H_{i}$ and $H_{j}$, respectively, which are
edge-disjoint. Therefore, since $e\in E(C_{i})$ and $Q_{j}^{\prime}\subseteq
F_{i}\setminus Q_{i}^{\prime}$, we must have that $e\notin E(Q_{j}^{\prime})$.
However, since $e\in E(C_{j})$ and $e\in E(F_{j})$ by definition, we must have
$e\in E(Q_{j}^{\prime})$, a contradiction.

Suppose now that $2r=k+1$. Let
$F_{1}\coloneqq\bigcup_{j=1}^{r}Q_{j}^{\prime}$, so $\Delta(F_{1})\leq r\Phi$
and it is $(\mathcal{U},\ell,s)$-good. By the conditioning above,
$((H^{*}_{1}\cup Q_{1})\setminus F_{1})\cup H_{1}\cup Q_{1}^{\prime}$ contains
a $(\mathcal{U},\ell^{2},s)$-good Hamilton cycle $C$ with $H_{1}\subseteq C$.
We split $C$ into two perfect matchings $M_{1}\cup M_{2}$ (observe that both
of them are $(\mathcal{U},\ell^{2},s)$-good) and redefine $H_{r}\coloneqq
H_{r}\cup\\{e\in M_{2}:\mathcal{U}\cap e\neq\varnothing\\}$, so that $H_{r}$
now satisfies (i). Now, for each $i\in\\{2,\ldots,r\\}$, we proceed as
follows. Let $F_{i}\coloneqq
M_{1}\cup\bigcup_{j=1}^{r}Q_{j}^{\prime}\cup\bigcup_{j=2}^{i-1}C_{j}$. It
follows by construction that $F_{i}$ is $(\mathcal{U},\ell,s)$-good and
$\Delta(F_{i})\leq r(\Phi+2)\leq(r+2)\Phi$. Then, by the conditioning above,
the graph $((H_{i}^{*}\cup Q_{i})\setminus F_{i})\cup H_{i}\cup
Q_{i}^{\prime}$ must contain a $(\mathcal{U},\ell^{2},s)$-good Hamilton cycle
$C_{i}$ with $H_{i}\subseteq C_{i}$. Take one such cycle and proceed. The fact
that the graphs $M_{1},C_{2},\ldots,C_{r}$ are pairwise edge-disjoint can be
proved as in the previous case. ∎

We now prove Theorem 1.5. Recall from Section 1.4 that, for any
$k\in\mathbb{N}$ and any graph $G\subseteq\mathcal{Q}^{n}$, we say that
$G\in\bm{\delta}k$ if $\delta(G)\geq k$, and $G\in\mathcal{HM}k$ if it
contains $\lfloor k/2\rfloor$ edge-disjoint Hamilton cycles and $k-2\lfloor
k/2\rfloor$ perfect matchings which are edge-disjoint from these cycles. We
say that $G\in\mathcal{P}k$ if, for every spanning subgraph
$H\subseteq\mathcal{Q}^{n}$ with $H\in\bm{\delta}k$, we have $G\cup
H\in\mathcal{H}\mathcal{M}k$.

###### Proof of Theorem 1.5.

The case $k=1$ of the statement was proved by Bollobás [12], so we may assume
$k\geq 2$. Let $0<\varepsilon\ll 1/k$ and
$G\sim\mathcal{Q}^{n}_{1/2-\varepsilon}$. By Theorem 1.8, we have
$\mathbb{P}[G\in\mathcal{P}k]=1-o(1)$. Also note that, by Lemma 4.2, we have
that $\mathbb{P}[e(G)\geq(1/2-\varepsilon/2)n2^{n-1}]=o(1)$. Hence,

$\mathbb{P}[\\{G\in\mathcal{P}k\\}\wedge\\{e(G)<(1/2-\varepsilon/2)n2^{n-1}\\}]=1-o(1).$

Thus, by a simple conditioning argument, there exists a positive integer
$m<(1/2-\varepsilon/2)n2^{n-1}$ such that

$\mathbb{P}[G\in\mathcal{P}k\mid e(G)=m]=1-o(1).$ (9.15)

Let $G_{m}\subseteq\mathcal{Q}^{n}$ be a uniformly random subgraph of
$\mathcal{Q}^{n}$ with exactly $m$ edges. Since
$\mathbb{P}[G\in\mathcal{P}k\mid e(G)=m]=\mathbb{P}[G_{m}\in\mathcal{P}k]$, by
(9.15) we have $\mathbb{P}[G_{m}\in\mathcal{P}k]=1-o(1)$. Now, because a.a.s.
$\tau_{\bm{\delta}k}(\tilde{\mathcal{Q}^{n}}(\sigma))\geq(1/2-\varepsilon/4)n2^{n-1}$,
the result follows. ∎

## References

  * Ajtai, Komlós and Szemerédi [1985] M. Ajtai, J. Komlós and E. Szemerédi, First occurrence of Hamilton cycles in random graphs, _Cycles in graphs (Burnaby, B.C., 1982)_ , vol. 115 of _North-Holland Math. Stud._ , 173–178, North-Holland, Amsterdam (1985).
  * Alon, Kim and Spencer [1997] N. Alon, J.-H. Kim and J. Spencer, Nearly perfect matchings in regular simple hypergraphs, _Israel J. Math._ 100 (1997), 171–187.
  * Alon and Spencer [2016] N. Alon and J. H. Spencer, _The probabilistic method_ , Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, fourth ed. (2016).
  * Alon and Krivelevich [2019] Y. Alon and M. Krivelevich, Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs, _arXiv e-prints_ (2019), 1912.01251.
  * Azuma [1967] K. Azuma, Weighted sums of certain dependent random variables, _Tôhoku Math. J. (2)_ 19 (1967), 357–367.
  * Balogh, Treglown and Wagner [2019] J. Balogh, A. Treglown and A. Z. Wagner, Tilings in randomly perturbed dense graphs, _Combin. Probab. Comput._ 28 (2019), 159–176.
  * Bhatt and Cai [1988] S. Bhatt and J.-Y. Cai, Take a walk, grow a tree, _29th Annual Symposium on Foundations of Computer Science (STOC)_ , 469–478 (1988).
  * Bhatt, Chung, Leighton and Rosenberg [1992] S. N. Bhatt, F. R. K. Chung, F. T. Leighton and A. L. Rosenberg, Efficient embeddings of trees in hypercubes, _SIAM J. Comput._ 21 (1992), 151–162.
  * Bohman, Frieze and Martin [2003] T. Bohman, A. Frieze and R. Martin, How many random edges make a dense graph Hamiltonian?, _Random Structures Algorithms_ 22 (2003), 33–42.
  * Bollobás [1983] B. Bollobás, The evolution of the cube, _Combinatorial mathematics (Marseille-Luminy, 1981)_ , vol. 75 of _North-Holland Math. Stud._ , 91–97, North-Holland, Amsterdam (1983).
  * Bollobás [1984] B. Bollobás, The evolution of sparse graphs, _Graph theory and combinatorics (Cambridge, 1983)_ , 35–57, Academic Press, London (1984).
  * Bollobás [1990] B. Bollobás, Complete matchings in random subgraphs of the cube, _Random Structures Algorithms_ 1 (1990), 95–104.
  * Bollobás [2020] B. Bollobás, personal communication (2020).
  * Bollobás and Frieze [1985] B. Bollobás and A. M. Frieze, On matchings and Hamiltonian cycles in random graphs, _Random graphs ’83 (Poznań, 1983)_ , vol. 118 of _North-Holland Math. Stud._ , 23–46, North-Holland, Amsterdam (1985).
  * Bollobás, Kohayakawa and Łuczak [1992] B. Bollobás, Y. Kohayakawa and T. Łuczak, The evolution of random subgraphs of the cube, _Random Structures Algorithms_ 3 (1992), 55–90.
  * Bollobás and Thomason [1985] B. Bollobás and A. Thomason, Random graphs of small order, _Random graphs ’83 (Poznań, 1983)_ , vol. 118 of _North-Holland Math. Stud._ , 47–97, North-Holland, Amsterdam (1985).
  * Borgs, Chayes, van der Hofstad, Slade and Spencer [2006] C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade and J. Spencer, Random subgraphs of finite graphs. III. The phase transition for the $n$-cube, _Combinatorica_ 26 (2006), 395–410.
  * Böttcher, Han, Kohayakawa, Montgomery, Parczyk and Person [2019] J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk and Y. Person, Universality for bounded degree spanning trees in randomly perturbed graphs, _Random Structures Algorithms_ 55 (2019), 854–864.
  * Böttcher, Montgomery, Parczyk and Person [2020] J. Böttcher, R. Montgomery, O. Parczyk and Y. Person, Embedding spanning bounded degree graphs in randomly perturbed graphs, _Mathematika_ 66 (2020), 422–447.
  * Burtin [1977] J. D. Burtin, The probability of connectedness of a random subgraph of an $n$-dimensional cube, _Problemy Peredači Informacii_ 13 (1977), 90–95.
  * Caha and Koubek [2007] R. Caha and V. Koubek, Spanning multi-paths in hypercubes, _Discrete Math._ 307 (2007), 2053–2066.
  * Chan and Lee [1991] M. Y. Chan and S.-J. Lee, On the existence of Hamiltonian circuits in faulty hypercubes, _SIAM J. Discrete Math._ 4 (1991), 511–527.
  * Chen [2013] X.-B. Chen, Paired many-to-many disjoint path covers of the hypercubes, _Inform. Sci._ 236 (2013), 218–223.
  * Dvořák and Gregor [2008] T. Dvořák and P. Gregor, Partitions of faulty hypercubes into paths with prescribed endvertices, _SIAM J. Discrete Math._ 22 (2008), 1448–1461.
  * Dvořák, Gregor and Koubek [2017] T. Dvořák, P. Gregor and V. Koubek, Generalized Gray codes with prescribed ends, _Theoret. Comput. Sci._ 668 (2017), 70–94.
  * Dyer, Frieze and Foulds [1987] M. E. Dyer, A. M. Frieze and L. R. Foulds, On the strength of connectivity of random subgraphs of the $n$-cube, _Random graphs ’85 (Poznań, 1985)_ , vol. 144 of _North-Holland Math. Stud._ , 17–40, North-Holland, Amsterdam (1987).
  * Erdős and Spencer [1979] P. Erdős and J. Spencer, Evolution of the $n$-cube, _Comput. Math. Appl._ 5 (1979), 33–39.
  * Espuny Díaz [tion] A. Espuny Díaz, _Hamiltonicity problems in random graphs_ , Ph.D. thesis, University of Birmingham (in preparation).