uniformly in $1\leq \ell \leq m$. Indeed,

-   either one of the two walks attains length $s=\lceil 2\log\log N\rceil$ before reaching an unpaired half-edge: there are at most $\ell-1<m$ possible trajectories to follow for each walk, so the conditional chance is at most $$2m2^{-s}=o(1).$$

-   or at least $t-2s$ unpaired half-edges are encountered, and the product of their degrees falls below $\frac{1}{\theta}$ with conditional probability at most $$\begin{aligned}
    \qquad \frac{4mt^2}N+{\ensuremath{\mathbb{P}}}\left(\prod_{k=1}^{t-2s}\deg(X_k^\star)< \frac 1{\theta}\right)& = & \Phi(\lambda)+o(1),\end{aligned}$$ by the same coupling as above and Berry-Essen’s inequality (\[lb:3\]).

Proof of Lemma \[lm:collisions\] {#sec:collisions}
================================

We denote by $\tau$ the (random) number of pairs formed during the exploration stage. For $k\geq 0$, we let ${\ensuremath{\mathfrak{U}}}_k$ denote the set of unpaired half-edges in the forest after $k\wedge\tau$ pairs have been formed, and we consider the random variable $$W_k:=\sum_{z\in{\ensuremath{\mathfrak{U}}}_k}{\ensuremath{\mathbf{w}}}(z).$$ Initially $W_0=2$, and this quantity either stays constant of decreases at each stage, depending on whether the condition appearing in step 3 is satisfied or not. More precisely, denoting by $z_k$ (resp. $z_k'$) the half-edge selected at step 1 (resp. chosen at step 2) of the $k^\textrm{th}$ pair, we have for all $k\geq 1$, $$\begin{aligned}
W_k & = & W_{k-1}-{\bf 1}_{(k\leq \tau)}\left({\ensuremath{\mathbf{w}}}(z_k){\bf 1}_{(z_k'\in {\ensuremath{\mathfrak{U}}}_{k-1}^+)}+{\ensuremath{\mathbf{w}}}(z_k'){\bf 1}_{(z_k'\in {\ensuremath{\mathfrak{U}}}_{k-1})}\right),\end{aligned}$$ where 