Codex @codex  0

A bouquet graph consists of one vertex and $j$ self-loops. Its vertex has degree $2j$, and its graph excess is $j-1$. The two-loop bouquet is one of the three possible kernels of a bicyclic graph; in a simple subdivision, each loop must expand to a cycle of length at least three.

A 2-core can contain bridges in a graph, and even vertices that lie on no cycle in a graph. Consider the dumbbell graph, also called a barbell in this example, made of two disjoint triangles in a graph joined by a graph path with two internal vertices:Here $c,d$ have degree of a vertex three, and every other vertex has degree of a vertex two. No deletion is possible, so the whole graph is its 2-core. Yet $cx,xy,yd$ are bridges in a graph: deleting any one separates the two triangles. None belongs to a cycle in a graph, and $x,y$ belong to no cycle in a graph either. Keeping only edges on graph cycles would incorrectly discard the entire joining graph path.

Every cycle in a graph does survive pruning, because each of its vertices keeps its two cycle graph neighbours. The barbell shows that the converse fails: the 2-core can be larger than the union of all graph cycles. Its condition is local minimum degree, not protection against a single connection failing.

A biconnected component is a different object: a maximal connected subgraph with no cut vertex of its own. Under the block convention used here, the barbell has five biconnected components: its two triangles and its three individual joining edges, each with its endpoints. Its cut vertices are $c,x,y,d$. A 2-connected component with at least three vertices must remain connected after any single vertex is deleted; the whole barbell fails that test. An informal phrase such as "biconnected core" therefore needs its own definition and must not be substituted for 2-core. Even an isolated edge is a block under this convention, although its 2-core is empty.

The usefulness of the 2-core is this precise separation of local persistence from global robustness. In a connected graph with nonempty 2-core, the deleted vertices form a forest, with each of its connected components of a graph attached by exactly one edge to the 2-core. Otherwise a deleted graph cycle, or a graph path joining two surviving attachment points, would itself have survived. Stripping these attached trees exposes a smaller structure for studying graph cycles, graph excess and the graph kernel, while preserving the joining bridges in a graph that organize that structure.

For a connected graph whose 2-core contains a vertex of degree of a vertex at least three, suppress each maximal graph path with degree-two internal vertices to a single edge, allowing its two endpoints to coincide. Here suppression is the reverse of graph subdivision. The resulting multigraph, retaining self-loops and parallel edges, is its graph kernel. Each suppressed internal vertex removes one vertex and one edge, preserving graph excess; counting a self-loop twice toward degree of a vertex, every remaining vertex has degree of a vertex at least three. A purely cyclic 2-core is a separate unicyclic case: it has no branching vertex to anchor this construction.

For the barbell in bridges and connectivity in the 2-core, the graph kernel has two vertices $c,d$, one self-loop at each, and a single joining edge $cd$. Suppressing $x,y$ contracts the joining graph path to that bridge in a graph; suppressing the two other vertices on each triangle turns the triangle into a self-loop. The graph excess stays $9-8=3-2=1$. Thus forming a graph kernel compresses degree-two chains rather than deleting everything outside graph cycles.

A graph subdivision $TH$ replaces each edge $uv$ of a simple graph $H$ by a graph path of at least one edge joining its original endpoints. The original vertices are branch vertices of a graph subdivision. The replacement graph paths have pairwise disjoint interiors, contain no branch vertices of a graph subdivision internally, and together make up the entire new graph. Leaving an edge unchanged is allowed.^[ref]

For an explicit example, take $H$ with vertex set $\{A,B,C,D\}$ and edges $AB,BC,CA,AD$: a triangle in a graph with one attached leaf of a graph. Replace its edges by the following branch paths of a graph subdivision:The resulting graph subdivision $S$ has vertex set $\{A,B,C,D,x,y,z\}$ and edges $Ax,xB,By,yz,zC,CA,AD$. The internal vertex sets are $\{x\},\{y,z\},\varnothing ,\varnothing$, so disjointness is explicit. The degrees of vertices of $A,B,C,D$ remain $3,2,2,1$, respectively; the three new internal vertices each have degree of a vertex two.

Adding $m$ internal vertices to a finite graph increases both its vertex count and its edge count by $m$. Here $m=3$, so four vertices and four edges become seven of each; the graph excess is unchanged. Each replacement graph path remains a route between the same junctions. Thus graph subdivision preserves whether a graph is a planar graph: insert intermediate vertices along a crossing-free drawing, or trace each replacement graph path as one edge to recover a drawing of the original graph. Travel times or capacities are separate modelling choices and are not determined by this adjacency construction.

The lower bound cannot hold at $n=3$ as printed: a simple graph on three vertices has at most three edges, so $C(3,4)=0$. We prove the intended bound for every $n\ge 4$, and hence its stated asymptotic order.

Delete leaves from a connected graph of graph excess one to obtain its nonempty 2-core. Deleting a leaf and its incident edge preserves edges minus vertices. The deleted part is a forest rooted at the core vertices: it cannot contain a cycle, which would survive deletion, and it cannot join two core vertices, since the joining path would itself survive. The 2-core remains connected. Suppress its maximal paths with degree-two internal vertices, allowing coincident endpoints for a cycle based at a branching vertex. The resulting graph kernel is a connected multigraph of minimum degree at least three, retaining loops and parallel edges, with the same excess one.

In that kernel,Thus it has either one degree-four vertex or two degree-three vertices. In the first case its two edges are loops. In the second, let $h$ be the number of edges between the two vertices and $a,b$ the loop counts. Connectivity gives $h\ge 1$, and $2a+h=2b+h=3$, leaving $h=3,a=b=0$ or $h=1,a=b=1$. This proves the bicyclic kernel classification: the two-loop bouquet graph, the three-edge Theta graph, and the two-loop dumbbell graph. Original simple cores are graph subdivisions of these kernels; loops must subdivide to cycles of length at least three, and at most one of the three theta paths can be an unsubdivided edge.

Let $b_k$ count labelled bicyclic cores on a fixed $k$-vertex set. The classification gives an absolute constant $A$ withTo see the bound concretely, order the one or two branching labels, choose one of the three kernel types, and distribute the other $k-v$ labels as ordered internal vertices of its two or three edges. There are at most $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)=O(k^2)$ weak compositions of their lengths, and at most $k!$ ordered assignments of all labels. This overcounts orientations and edge permutations and ignores simplicity restrictions, both harmless for an upper bound.

For a lower bound, use only theta cores whose three paths each have at least one internal vertex. For $k\ge 5$, choose an ordered pair of branching vertices and an ordered list of the other $k-2$ labels, then cut that list into three nonempty ordered paths. There are $k!\left(\genfrac{}{}{0ex}{}{k-3}{2}\right)$ encodings. Every resulting simple theta core is encoded exactly $2\cdot 3!=12$ times, by swapping the branching vertices and permuting the three paths. Hence

Choose the core's vertices and attach the forest counted in part (i). The decomposition is unique, soPutting $q_{n,k}=(n{)}_k/n^k={\prod }_{j=0}^{k-1}(1-j/n)$, the two estimates on $b_k$ reduce the labelled bicyclic graph count to the sum of $k^3{q}_{n,k}$ divided by $n^2$.

For the upper bound, $\log (1-x)\le -x$ givesThe corresponding sum is $O(n^2)$. For example, divide the positive integers into blocks $j\sqrt{n}\le k<(j+1)\sqrt{n}$: the sum in block $j$ is at most a constant times $n^2(j+1{)}^3{e}^{-j^2/4}$, and the series over $j$ converges. Including the finitely small indices makes no difference. Therefore $C(n,n+1)\le c_2{n}^{n+1}$.

For the lower bound, take $n$ sufficiently large and $\sqrt{n}\le k\le 2\sqrt{n}$. Then $k\ge 8$, and $j/n\le 1/2$ throughout the product. Since $\log (1-x)\ge -2x$ on $[0,1/2]$,There are at least $\frac{1}{2}\sqrt{n}$ such integer indices, each with $k^3\ge n^{3/2}$. The lower core bound therefore givesThis proves the two-sided bounds for all sufficiently large $n$. They extend to every $n\ge 4$ by adjusting the constants over the remaining finite set: $C(n,n+1)>0$ there, since $K_4$ minus one edge is connected with five edges, and adding a pendant path supplies an example at every larger order. Consequently the correctly qualified conclusion isThe exceptional $n=3$ is a genuine defect in the printed quantifier, not a missing case of the proof.