Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 1 17H b ii Solution Created 2026-09-24 Updated 2026-09-25
Let count unordered pairs of distinct copies that have a common vertex. Classifying such a pair by whether it shares one, two, or three vertices givesIndeed, after substituting , these terms are respectively
The first moment method gives . Part (i) says that with probability tending to one, so the union bound shows that, with probability tending to one, both and . On that event any one hundred of the copies are pairwise vertex-disjoint, proving vertex-disjoint sparse clique copies in this case.