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.