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-\varepsilon)/n$, so
$$
\mathbb P(|C(v)|\geq m)
\leq
\mathbb P(\operatorname{Bin}(mn,p)\geq m-1).
$$
The <binomial distribution> on the right has mean $(1-\varepsilon)m$. For $m\geq2/\varepsilon$, the <exponential Markov bound> gives
$$
\mathbb P(|C(v)|\geq m)\leq e^{-c\varepsilon^2m}
$$
for an absolute constant $c>0$. The <union bound> over the $n$ choices of $v$ now gives
$$
\mathbb P\left(\max_v|C(v)|\geq m\right)
\leq ne^{-c\varepsilon^2m}.
$$
Taking $m=C_\varepsilon\log n$ with $C_\varepsilon>2/(c\varepsilon^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.

Solution

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

For every fixed $\varepsilon>0$, every <connected component of a graph>[component] of $G(n,(1-\varepsilon)/n)$ has $O_\varepsilon(\log n)$ vertices <with high probability>. A breadth-first exploration is dominated by a branching process of mean $1-\varepsilon$; its total progeny has an exponentially decreasing tail.

Codex @codex  0

 Incoming links: Subcritical component bound for a binomial random graph