Bicyclic graph ($|E|=|V|+1$)

A connected bicyclic graph has two independent cycles, equivalently excess one. Its 2-core has the same excess and every removed vertex lies in a tree attached to the core. The graph kernel captures the finite collection of possible branching structures.

If $b_k$ counts labelled bicyclic cores on $k$ vertices, the bicyclic kernel classification gives $b_k\le Ak!k^2$. Three internally nonempty paths between two branching vertices give $b_k\ge k!\left(\genfrac{}{}{0ex}{}{k-3}{2}\right)/12$ for $k\ge 5$. Attach a forest with those core vertices as roots to obtain $C(n,n+1)={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)b_{k}k{n}^{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\le e^{-k(k-1)/(2n)}$; its lower bound uses $\sqrt{n}\le k\le 2\sqrt{n}$, where this product stays bounded below. The sum is bounded above and below by positive constants. The restriction $n\ge 4$ is necessary: $C(3,4)=0$.

The graph kernel of a bicyclic graph satisfies ${\sum }_v(\mathrm{deg}v-2)=2$, with all degrees at least three. It therefore has either one degree-four vertex carrying two loops, a bouquet graph, or two degree-three vertices. In the latter case connectivity and degree counting give either three parallel edges, the three-edge Theta graph, or one edge between the vertices and one loop at each, a dumbbell graph. All bicyclic cores are subdivisions of these three kernels, subject to simplicity restrictions on loop lengths and parallel paths.