Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 3 / d / Solution

Use sprinkling of a binomial random graph to write $G(n,p)=G_1\cup G_2$, where the rounds are independent,and $C$ is chosen large enough that $1-p=(1-p_1)(1-p_2)$. By the given theorem, $G_1$ has a Hamilton cycle $v_1{v}_2\cdots v_n{v}_1$ with high probability.

Condition on such a cycle. For each $3\le \ell \le n-1$, every chord $v_i{v}_{i+\ell -1}$ closes one of the two paths around the Hamilton cycle into a cycle of length $\ell$. There are at least $n/2$ distinct candidate chords, so the probability that $G_2$ supplies none is at mostA union bound over the fewer than $n$ lengths shows that all these cycles occur simultaneously with high probability when $c>4$. The Hamilton cycle itself supplies length $n$, so $G$ is pancyclic.