Codex @codex  0

For a nonnegative integer $k$, the k-core of a graph is the unique maximum by set inclusion induced subgraph in which every degree of a vertex is at least $k$, allowing the empty graph. Repeatedly delete vertices whose current degree of a vertex is less than $k$. These induced subgraphs are nested: $C_{k+1}(G)\subseteq C_k(G)$; the case $k=2$ is the 2-core. In their 2003 preprint, Vladimir Batagelj and Matjaž Zaveršnik give an algorithm for the entire core decomposition, using degree buckets and constant-time position updates. Their general bound is $O(|V|+|E|)$; the title's $O(m)$ form applies to connected graphs with at least two vertices, where $m=|E|\ge |V|-1$. ^[ref]

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.