2-core of a graph ($C_2(G)$)

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph $G=(V,E)$, its 2-core is the unique maximum by set inclusion induced subgraph $G[S]$ such thatThe empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that $S$ contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let $ab$ denote the edge $\{a,b\}$ and takeThe triangle in a graph $abc$ has a branching tail attached at $c$, and $z$ is an isolated vertex. In alphabetical order the initial degrees of vertices are $(2,2,3,3,2,1,1,0)$. Deleting $f$ turns $e$ into a leaf of a graph; deleting $g$ leaves $d$ with degree of a vertex two; deleting $z$ changes no other degree of a vertex. Now delete $e$, which makes $d$ a leaf of a graph, and finally delete $d$. Exactly the three edges of $abc$ remain: $C_2(G)=G[\{a,b,c\}]$.

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

Use adjacency lists and a FIFO queue to implement the deletion rule in time complexity $O(|V|+|E|)$. Compute each initial degree of a vertex once, mark every vertex alive, and put all vertices of degree of a vertex zero or one in the FIFO queue. Each vertex is inserted at most once. Repeatedly remove the front vertex $v$, mark it dead, and traverse its original adjacency list. For each still-alive graph neighbour $u$, decrease the stored degree of a vertex of $u$ by one; if it has just become one, append $u$. A vertex already queued can drop from one to zero before its turn, but it stays queued and requires no second insertion. Stop when the FIFO queue is empty; the alive vertices induce $C_2(G)$.

For the displayed example, initially enqueue $(f,g,z)$ in that order. The successive FIFO queues, after each deletion and all its updates, areThis explains the delayed deletion of $d$: its initial degree of a vertex was three, but the relevant degree of a vertex is always its current one in the surviving induced subgraph. Removing only the original vertices of degree of a vertex one would give the wrong answer.

Initialization inspects every vertex and every adjacency list entry once. During deletion each original adjacency list is traversed at most once, so at most $2|E|$ entries are inspected in an undirected graph. All insertions, removals and stored-degree updates cost constant time each. Thus total time complexity is $O(|V|+|E|)$ and additional storage, beyond the adjacency lists, is $O(|V|)$. The cost includes isolated vertices; repeatedly rescanning the whole surviving graph after each deletion would lose this bound. The single-threshold FIFO queue method is enough for the 2-core; the full k-core of a graph decomposition computes all thresholds.

Suppose $T$ is any vertex set whose induced subgraph has every degree of a vertex at least two. No vertex of $T$ can be the first one deleted from $T$: before such a deletion it still has its two graph neighbours within $T$, contradicting eligibility for deletion. Consequently every qualifying $T$ survives every legal deletion sequence. Once deletion stops, its remainder $R$ itself qualifies, because every surviving vertex has at least two surviving graph neighbours. Therefore $T\subseteq R$ for every qualifying $T$: $G[R]$ is the unique maximum and the final remainder is independent of deletion order. The intermediate FIFO queues and deletion orders can differ.

There is also a direct existence argument. If $A$ and $B$ qualify, then $A\cup B$ qualifies: each vertex retains at least the two graph neighbours it already had in $A$ or in $B$. Taking the union of all qualifying vertex sets produces the maximum. This rules out a collection of competing, incomparable inclusion-maximal answers. It also explains why restricting the search to connected subgraphs would change the question.

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.