Solution

ID: 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 , where the rounds are independent,
and is chosen large enough that . By the given theorem, has a Hamilton cycle with high probability.
Condition on such a cycle. For each , every chord closes one of the two paths around the Hamilton cycle into a cycle of length . There are at least distinct candidate chords, so the probability that supplies none is at most
A union bound over the fewer than lengths shows that all these cycles occur simultaneously with high probability when . The Hamilton cycle itself supplies length , so is pancyclic.

New to topics? Read the docs here!