$G(\pi)$ starting from any $x\in{\ensuremath{\mathcal{X}}}$ satisfies $$\begin{aligned}
\label{toshow}
{\ensuremath{\mathbb{P}}}\left(X_t\textrm{ is not a root}\right) & \leq & 2^{1-t},\end{aligned}$$ for all $t\leq r-h$. The claim is trivial if the ball of radius $r$ around $x$ is acyclic. Otherwise, it contains a single cycle $\mathcal{C}$, by assumption. Write $d(z,\mathcal{C})$ for the minimum length of a non-backtracking path from $x$ to some $z\in \mathcal{C}$. The non-backtracking property ensures that if $d(X_{t},\mathcal{C})<d(X_{t+1},\mathcal{C})$ for some $t<r-h$, then $X_{t+1},X_{t+2},\ldots,X_{r-h}$ are all roots. By (\[assume:delta\]), the conditional chance that $d(X_{t+1},\mathcal{C})=d(X_t,\mathcal{C})+1$ given the past is at least $1/2$ (unless $d(X_t,\mathcal{C})=1$, which can only happen once). This shows (\[toshow\]). We then specialize to $t=h$.

The exposure process {#sec:exposure-process}
====================

The remainder of the paper is devoted to the proof of Proposition \[pr:up\]. Fix two distinct half-edges $x,y\in{\ensuremath{\mathcal{X}}}$. We describe a two-stage procedure that generates a uniform pairing on ${\ensuremath{\mathcal{X}}}$ together with a rooted forest ${\ensuremath{\mathfrak{F}}}$ keeping track of certain paths from $x$ and $y$. Initially, all half-edges are unpaired and ${\ensuremath{\mathfrak{F}}}$ is reduced to its two roots, $x$ and $y$. We then iterate the following three steps:

1.  An unpaired half-edge $z\in{\ensuremath{\mathfrak{F}}}$ is selected according to some rule (see below).

2.  $z$ is paired with a uniformly chosen other unpaired 