= Labelled bicyclic graph count
{title2=$C(n,n+1)=\Theta(n^{n+1})\quad(n\geq4)$}
If $b_k$ counts labelled bicyclic cores on $k$ vertices, the <bicyclic kernel classification> gives $b_k\leq A k!k^2$. Three internally nonempty paths between two branching vertices give $b_k\geq k!\binom{k-3}{2}/12$ for $k\geq5$. Attach a forest with those core vertices as roots to obtain $C(n,n+1)=\sum_k\binom nk b_kkn^{n-k-1}$. After division by $n^{n+1}$ the relevant sum is $n^{-2}\sum_k k^3(n)_k/n^k$. Its upper bound follows from $(n)_k/n^k\leq e^{-k(k-1)/(2n)}$; its lower bound uses $\sqrt n\leq k\leq2\sqrt n$, where this product stays bounded below. The sum is bounded above and below by positive constants. The restriction $n\geq4$ is necessary: $C(3,4)=0$.
Back to article page
