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 attacking a carefully chosen 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 attacked (i. e. disabled) nodes. My problem is 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 attack 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.