Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 1

Explore the connected component of a graph containing a fixed vertex $v$ by Breadth-first search. If the exploration discovers at least $m$ vertices, then before its $m$th discovery at least $m-1$ of at most $mn$ tested potential edges must be present. The tests are independent Bernoulli trials with parameter $p=(1-\epsilon )/n$, soThe binomial distribution on the right has mean $(1-\epsilon )m$. For $m\ge 2/\epsilon$, the exponential Markov bound givesfor an absolute constant $c>0$. The union bound over the $n$ choices of $v$ now givesTaking $m=C_{\epsilon }\log n$ with $C_{\epsilon }>2/(c{\epsilon }^2)$ makes this probability tend to zero. This proves the subcritical component bound for a binomial random graph.

Solved by gpt-5.6-sol high.

A connected graph on $s$ vertices containing at least two cycles has a spanning tree together with at least two further edges. By Cayley formula, the number of labelled spanning trees on a fixed $s$-set is $s^{s-2}$. Hence the first moment method and a union bound show that the probability of such a component of order $s$ is at mostwhere $p=(1-\epsilon )/n$ and $C$ is absolute. Requiring that the chosen set be a component would only add absent-edge conditions, so omitting them is a valid upper bound.

ThereforeThus every component in the stated range is either a tree or a unicyclic component with high probability.

Solved by gpt-5.6-sol high.

The sharp Hamilton cycle threshold for the Erdős-Rényi model says thatonly above the window $np=\log n+\log \log n+o(1)$. The hypothesis therefore places $p(n)$ above that window. The Hamiltonicity-to-pancyclicity sprinkling principle then says that three independent $G(n,p(n))$ rounds contain every cycle graph $C_{\ell }$, $3\le \ell \le n$, with high probability: one round supplies a Hamilton cycle, while the other two supply the chords and short-cycle edges used to obtain all intermediate lengths.

The union of the three rounds has individual edge probabilityBy the standard monotone coupling, it is a subgraph of $G(n,3p(n))$. Since being pancyclic is an increasing graph property, the required probability tends to one. If $3p(n)>1$, interpret the latter parameter as $\min \{3p(n),1\}$, in which case the conclusion is immediate.

Solved by gpt-5.6-sol high.