K-core peeling invariant
= K-core peeling invariant
During repeated deletion of vertices of current degree below $k$, every subgraph of minimum degree at least $k$ is contained in the active induced subgraph. If an active vertex has degree below $k$, its degree in any subgraph of the active graph is no greater, so no candidate can contain it. This proves the invariant inductively. A queue of threshold crossings and <adjacency lists> implements peeling in $O(|V|+|E|)$ time.