half-edge $z'$.

3.  If neither $z'$ nor any of its neighbours was already in ${\ensuremath{\mathfrak{F}}}$, then all neighbours of $z'$ become children of $z$ in the forest ${\ensuremath{\mathfrak{F}}}$.

The *exploration stage* stops when no unpaired half-edge is compatible with the selection rule. We then complete the pairing by matching all the remaining unpaired half-edges uniformly at random: this is the *completion stage*.

The condition in step $3$ ensures that ${\ensuremath{\mathfrak{F}}}$ remains a forest: any $z\in{\ensuremath{\mathfrak{F}}}$ determines a unique sequence $(z_0,\ldots,z_h)$ in ${\ensuremath{\mathfrak{F}}}$ such that $z_0$ is a root, $z_{i}$ is a child of $z_{i-1}$ for each $1\leq i\leq h$, and $z_h=z$. We shall naturally refer to $h$ and $z_0$ as the *height* and *root* of $z$, respectively. We also define the *weight* of $z$ as $${\ensuremath{\mathbf{w}}}(z):=\prod_{i=1}^h\frac 1{\deg(z_i)}.$$ Note that this quantity is the quenched probability that the sequence $(z_0,\ldots,z_h)$ is realized by a <span style="font-variant:small-caps;">nbrw</span> on $G$ starting from $z_0$. In particular, $$\begin{aligned}
\label{wbound}
{\ensuremath{\mathbf{w}}}(z) & \leq & P^h(z_0,z).\end{aligned}$$ $$\begin{aligned}
\label{wbound}
P^{t}(x,\pi(y)) & \geq & \sum_{(u,v)\in{\ensuremath{\mathcal{H}}}_{x}\times{\ensuremath{\mathcal{H}}}_{y}}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v){\bf 1}_{(\pi(u)=v)},\end{aligned}$$ where ${\ensuremath{\mathcal{H}}}_x$ (resp. ${\ensuremath{\mathcal{H}}}_y$) denotes the set of unpaired half-edges with height $\frac{t}{2}$ and root $x$ (resp. $y$) in ${\ensuremath{\mathfrak{F}}}$ at the end of the exploration stage. Our rule for step 1 consists 