= 2-core of a graph
{title2=$C_2(G)$}
= Graph 2-core
{synonym}
= 2-core
{synonym}
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 that
$$
\deg_{G[S]}(v)\geq2\qquad\text{for every }v\in S.
$$
The 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. <An O(m) Algorithm for Cores Decomposition of Networks by Vladimir Batagelj and Matjaž Zaveršnik>[Batagelj and Zaveršnik, An O(m) Algorithm for Cores Decomposition of Networks, §2, definition of a core]{ref}
For a complete worked example, let $ab$ denote the <edge> $\{a,b\}$ and take
$$
V=\{a,b,c,d,e,f,g,z\},\qquad E=\{ab,bc,ca,cd,de,ef,dg\}.
$$
The <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\}]$.
\Image[/graph-two-core-leaf-pruning-trace.png]
{title=The complete <leaf pruning for the 2-core> trace: each panel recomputes the displayed <degrees of vertices> from the surviving <induced subgraph>, while the <FIFO queue> determines the next deletion}
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.
Back to article page
