with $\lambda=\frac{4}{|{\ensuremath{\mathcal{I}}}|}$, $b=2\theta$ and $c=4 m \theta$.

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

We may fix $z_0\in\{x,y\}$ and restrict our attention to the halved sum $$Z:=\sum_{z\in{\ensuremath{\mathfrak{F}}}}{\ensuremath{\mathbf{w}}}(z){\bf 1}_{({\ensuremath{\mathbf{w}}}(z)<{{w_{\textsc{min}}}})}{\bf 1}_{(z\textrm{ has root }z_0)}.$$ Consider $m=\lfloor\log N\rfloor$ independent <span style="font-variant:small-caps;">nbrw</span>s on $G(\pi)$ starting at $z_0$, each being killed as soon as its weight falls below ${{w_{\textsc{min}}}}$, and write $A$ for the event that their trajectories form a tree of height less than $t/2$. Clearly, ${\ensuremath{\mathbb{P}}}\left(A|\pi\right)\geq Z^m.$ Taking expectation and using Markov inequality, we deduce that $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left(Z>\varepsilon\right) & \leq & \frac{{\ensuremath{\mathbb{P}}}\left(A\right)}{\varepsilon^m},\end{aligned}$$ where the average is now taken over both the walks and the pairing. Recalling that $m=\lceil \log N\rceil$, it is more than enough to establish that ${\ensuremath{\mathbb{P}}}(A)  =  \left(o(1)\right)^m.$ To do so, we generate the $m$ killed <span style="font-variant:small-caps;">nbrw</span>s one after this other, revealing the underlying pairs along the way, as described in Section \[sec:lower-bound\]. Given that the first $\ell-1$ walks form a tree of height less than $t/2$, the conditional chance that the $\ell^\textrm{th}$ walk also fulfils the requirement is $o(1)$, uniformly in $1\leq\ell\leq m$. Indeed,

-   either its weight falls below $\eta=(1/{\log N})^{2}$ before it ever reaches an unpaired half-edge: thanks to the tree structure, there are at most $\ell-1< 