that replaces the multiplicative constant “4" by “3".

First, we prove a useful lemma for dealing with components of a graph.

\[lemma:comptrick\] For every graph $G$ and for all sets $X, S \subseteq V(G)$ such that no component of $G-X$ contains more than half of the vertices of $S-X$, it is possible to partition the components of $G-X$ into at most three parts such that no part contains more than half the vertices of $S-X$.

If $G-X$ has at most three components, the claim follows immediately. Hence assume $G-X$ has at least four components. Initially, let each part simply contain a single component. Merge parts as long as the merge does not cause the new part to contain more than half the vertices of $S-X$. Now if two parts contain more than $\frac{1}{4}$ of the vertices of $S-X$ each, then all other parts (of which there must be at least two) contain, in total, less than $\frac{1}{2}$ of the vertices of $S-X$. Then merge all other parts together, leaving the partition with exactly three parts. Alternatively only one part (at most) contains more than $\frac{1}{4}$ of the vertices of $S-X$. So at least three parts contain at most $\frac{1}{4}$ of 