Codex @codex  0

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.

We first establish the labelled forest count with prescribed roots. For a prescribed root set $R$ of size $k<n$, orient each tree toward its unique root. Repeatedly delete the smallest remaining nonroot leaf, recording its parent. There are $n-k$ deletions, and the final recorded parent belongs to $R$. Conversely, start with any code of length $n-k$ whose last entry lies in $R$. At each step select the smallest remaining nonroot absent from the remaining code, connect it to the code's first entry, and delete that vertex and entry. Such a vertex exists: among $s$ remaining nonroots, the remaining code has $s$ entries but at least its last entry is a root, so at most $s-1$ nonroots occur in it. Previously deleted vertices never recur in the code, so the selected parent is still present. Every edge goes from a vertex being deleted to one retained, excluding a cycle. The resulting forest has one root in each graph component, and the two constructions are inverse. Its count is thereforefor $k=n$, interpret this as one, the empty forest.

A connected simple graph with $n$ edges has exactly one cycle: a spanning tree uses $n-1$ edges, and the remaining edge creates its unique cycle. If that graph cycle has length $k$, choose its vertex set in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways and its unoriented cyclic order in $(k-1)!/2$ ways. All other edges form a forest rooted at those $k$ vertices, with exactly one cycle vertex per forest component; two roots in one attached component would create an additional cycle. Conversely every such cycle and rooted forest gives a unique unicyclic component. ThusThis is the labelled unicyclic graph count. The term $k=n$ correctly counts a cycle with no attached nonroot vertices.

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 mostwhere $p=(1-\epsilon )/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.

ThereforeThus every component in the stated range is either a tree or a unicyclic component with high probability.

A pseudoforest is an undirected graph in which every connected component of a graph contains at most one cycle in a graph. Thus each component is a tree or a unicyclic component. A finite tree component has one fewer edge than vertices; a finite unicyclic component has equally many edges and vertices.