that the second sum is $o_{\ensuremath{\mathbb{P}}}(1)$ uniformly in $x\in{\ensuremath{\mathcal{R}}}$, it suffices to bound its summands by $1/N$ and observe that $|{\ensuremath{\mathcal{B}}}_x|  \leq  \Delta^h = o( N)$ by (\[def:h\]), while $$\begin{aligned}
|{\ensuremath{\mathcal{X}}}\setminus{\ensuremath{\mathcal{R}}}| & = & \sum_{x\in{\ensuremath{\mathcal{X}}}}P^h(x,{\ensuremath{\mathcal{X}}}\setminus{\ensuremath{\mathcal{R}}}),\end{aligned}$$ ($P$ is doubly stochastic), which is $o_{\ensuremath{\mathbb{P}}}(N)$ uniformly in ${\ensuremath{\mathcal{X}}}$ by Proposition \[pr:root\].

Define $r:=\left\lfloor\frac{\log N}{5\log \Delta}\right\rfloor$ and fix $x\in{\ensuremath{\mathcal{X}}}$. The ball of radius $r$ around $x$ can be generated sequentially, its half-edges being paired one after the other with uniformly chosen other unpaired half-edges, until the whole ball has been paired. Observe that at most $k=\frac{\Delta\left((\Delta-1)^{r}-1\right)}{\Delta-2}$ pairs are formed. Moreover, for each of them, the number of unpaired half-edges having an already paired neighbour is at most $\Delta(\Delta-1)^r$ and hence the conditional chance of hitting such an half-edge (thereby creating a cycle) is at most $p=\frac{\Delta(\Delta-1)^r-1}{N-2k-1}$. Thus, the probability that more than one cycle is found is at most $$\begin{aligned}
(kp)^2 & = & O\left(\frac{(\Delta-1)^{4r}}{N^2}\right)\ = \ o\left(\frac{1}{N}\right).\end{aligned}$$ Summing over all $x\in{\ensuremath{\mathcal{X}}}$ (union bound), we obtain that with high probability, no ball of radius $r$ in $G(\pi)$ contains more than one cycle.

To conclude the proof, we now fix a pairing $\pi$ with the above property, and we prove that the <span style="font-variant:small-caps;">nbrw</span> on 