in selecting an half-edge with maximal weight[^3] among all unpaired $z\in{\ensuremath{\mathfrak{F}}}$ with height ${\ensuremath{\mathbf{h}}}(z)<t/2$ and weight ${\ensuremath{\mathbf{w}}}(z)>{{w_{\textsc{min}}}}$, where $${{w_{\textsc{min}}}}:=N^{-\frac 23}.$$ The only role of this parameter is to limitate the number of pairs formed during the exploration stage. As outlined in Section \[sec:outline\], we shall be interested in $$\begin{aligned}
{\ensuremath{\mathfrak{W}}}& := & \sum_{(u,v)\in{\ensuremath{\mathcal{H}}}_x\times{\ensuremath{\mathcal{H}}}_y}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v){\bf 1}_{{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\leq \theta},\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, and where $$\begin{aligned}
\label{def:theta}
\theta & := & \frac{1}{N(\log N)^2}.\end{aligned}$$ Write ${\overline{\ensuremath{\mathfrak{W}}}}$ for the quantity obtained by replacing $\leq$ with $>$ in ${\ensuremath{\mathfrak{W}}}$, so that $$\begin{aligned}
{\ensuremath{\mathfrak{W}}}+{\overline{\ensuremath{\mathfrak{W}}}}& = & \sum_{(u,v)\in{\ensuremath{\mathcal{H}}}_x\times{\ensuremath{\mathcal{H}}}_y}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\\
& \geq & \sum_{z\in{\ensuremath{\mathcal{H}}}_x\cup{\ensuremath{\mathcal{H}}}_y}{\ensuremath{\mathbf{w}}}(z)-1,\end{aligned}$$ thanks to the inequality $ab\geq a+b-1$ for $a,b\in[0,1]$. Now, let ${\ensuremath{\mathfrak{U}}}$ denote the set of unpaired half-edges in ${\ensuremath{\mathfrak{F}}}$. By construction, at the end of the exploration stage, each $z\in{\ensuremath{\mathfrak{U}}}$ must have height $t/2$ or weight less than ${{w_{\textsc{min}}}}$, so that $$\begin{aligned}
{\ensuremath{\mathfrak{W}}}+{\overline{\ensuremath{\mathfrak{W}}}}& \geq & \sum_{z\in{\ensuremath{\mathfrak{U}}}}{\ensuremath{\mathbf{w}}}(z)-\sum_{z\in{\ensuremath{\mathfrak{F}}}}{\ensuremath{\mathbf{w}}}(z){\bf 1}_{({\ensuremath{\mathbf{w}}}(z)<{{w_{\textsc{min}}}})}-1.\end{aligned}$$ Therefore, Proposition \[pr:up\] follows from the following four technical lemmas.

\[lm:completion\] For every $\varepsilon>0$, $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left(P^{t}(x,\pi(y))\leq \frac{{\ensuremath{\mathfrak{W}}}-\varepsilon}{N}\right) & = & o\left(\frac 1{N^2}\right)\, .
$$

\[lm:small\] For every $\varepsilon>0$, $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left(\sum_{z\in{\ensuremath{\mathfrak{F}}}}{\ensuremath{\mathbf{w}}}(z){\bf 1}_{({\ensuremath{\mathbf{w}}}(z)<{{w_{\textsc{min}}}})}>\varepsilon\right)  & = & o\left(\frac 1{N^2}\right)\, .\end{aligned}$$

