A target system is modelled as a giant, undirected, simple graph G (no hyperedge) that can be scrutinized in adequate detail to budget and plan the attack: its topology changes slowly w/r to the time it takes to complete the attack. Although the graph has size |G| >> 1, it is sparse: all its nodes have degree O(1).

An attack against the graph consists in carefully choosing a subset of its nodes to disable them; that is, to cut all their incident edges. The attack is successful if the remaining subgraph has all its connected components of size o(|G|). The cost of the attack is the total number of disabled nodes. I seek to establish that the graph will sustain any attack as long as the attacker only accepts a cost o(|G|).

Since it would be pointless to disable a node of degree 1 or 2, assume WLOG that suitable preprocessing has reduced the graph G to its 3-kernel: the largest minor containing neither loops, nor redundant (multiple) edges, nor any subgraph that is a rooted tree or a chain. In particular G has only nodes of degree >= 3. To make the problem interesting, assume planarity analysis will not help any further.

Now, my question: is it true that, against a given connected kernel "in general position", successful attacks cost at least 1/4 - o(1) of its nodes, a tight estimate when the graph is 3-regular? Else, is there a non-trivial lower bound on the cost?

By "in general position", I mean the attacker can only collect O(1) statistics about the graph, such as # of nodes of degree j for each j (of which only O(1) are non-zero), or # of edges connecting a node of degree j to a node of degree j'; then, they must postulate their assigned target is just any random instance from amongst a parametric family of graphs, one that happens to match the statistics at hand.