Dismantling sparse random graphs

Svante Janson, Andrew Thomason

We consider the number of vertices that must be removed from a graph G in order that the remaining subgraph has no component with more than k vertices. Our principal observation is…