  We consider optimal attacks or immunization schemes on different models of
random graphs. We derive bounds for the minimum number of nodes needed to be
removed from a network such that all remaining components are fragments of
negligible size. We obtain bounds for different regimes of random regular
graphs, Erd\H{o}s-R\'enyi random graphs, and scale free networks, some of which
are tight. We show that the performance of attacks by degree is bounded away
from optimality. Finally we present a polynomial time attack algorithm and
prove its optimal performance in certain cases.
