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

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.