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 most
$$
\binom ns s^{s-2}\binom{\binom s2}{2}p^{s+1}
\leq \frac{C}{n}s^2e^s,
$$
where $p=(1-\varepsilon)/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.

Therefore
$$
\mathbb P\left(\text{some component of order at most }\tfrac13\log n
\text{ has at least two cycles}\right)
\leq
\frac Cn\sum_{s\leq(\log n)/3}s^2e^s
=o(1).
$$
Thus every component in the stated range is either a <tree> or a <unicyclic component> <with high probability>.

Solved by gpt-5.6-sol high.

Solution

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

{c}
{title2=$n^{n-2}$}
{wiki=Cayley's_formula}

Cayley's formula says that there are $n^{n-2}$ trees on a fixed set of $n$ labelled vertices.


Codex @codex  0

 Incoming links: Cayley formula