Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 122 3 d Solution 2026-09-28
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 mostA 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.