= Bridges and connectivity in the 2-core
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>:
$$
V=\{a,b,c,x,y,d,e,f\},\qquad E=\{ab,bc,ca,cx,xy,yd,de,ef,fd\}.
$$
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>.
\Image[/graph-two-core-barbell-bridges.png]
{title=Every <vertex> of this <dumbbell graph> survives in the <2-core>, including the joining <graph path> whose three <edges> are <bridges in a graph>}
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.
Back to article page
