= Solution
In the standard labelled encoding of a pointed <planar quadrangulation>, incidences at the distinguished vertex are represented by visits counted by the record variables $G_m$. Consequently its <degree of a vertex> is bounded by the largest such count encountered before the coding walk first reaches $-1$.
Before time $2n+1$ there are at most $2n+1$ possible record levels. The <union bound> and part i therefore imply
$$
\mathbb P\left(\max_mG_m\geq r,\ \sigma=2n+1\right)
\leq(2n+1)\left(\frac56\right)^{r-1}.
$$
Conditioning on $\sigma=2n+1$ and using the supplied lower bound gives
$$
\mathbb P\left(\deg(v^*)\geq r\mid\sigma=2n+1\right)
\leq C_0n^{5/2}\left(\frac56\right)^{r-1}.
$$
Set $r=C\log n$. If $C>5/(2\log(6/5))$, the right-hand side tends to zero. Hence for some constant $C>0$,
$$
\boxed{\mathbb P(\deg(v^*)\leq C\log n)\longrightarrow1}.
$$
Back to article page
