 k-core of a graph

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]