 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 implyConditioning on $\sigma =2n+1$ and using the supplied lower bound givesSet $r=C\log n$. If $C>5/(2\log (6/5))$, the right-hand side tends to zero. Hence for some constant $C>0$,