= Solution
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>.
Back to article page
