Subcritical component bound for a binomial random graph

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

For fixed $0<\lambda <1$ in $G(n,\lambda /n)$, the largest component of a graph has the displayed order with high probability. A dominating Galton-Watson process gives the tail bound $\mathbb{P}(T\ge j)\le e^{-(\lambda -1-\log \lambda )(j-1)}$ by the exponential Markov inequality. For the lower bound, the tree-component expectation in the Erdős-Rényi model diverges at $j=\lfloor (1-\eta )\log n/(\lambda -1-\log \lambda )\rfloor$. The disjoint-set covariance factor and the exclusion of overlaps give relative variance tending to zero, so the second moment method supplies a tree component of that order.

A connected graph is unicyclic when it contains exactly one cycle, equivalently when its numbers of vertices and edges agree.

A pseudoforest permits both these components and acyclic tree components.

A labelled unicyclic component has a unique cycle of length $k\ge 3$, with a rooted forest attached to its vertices. Choose its vertices in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways and its unoriented cycle in $(k-1)!/2$ ways. The labelled forest count with prescribed roots gives $k{n}^{n-k-1}$ attachments. Summing over $k$ and putting $j=n-k$ yields the displayed identity.