Given a graph $G$ on $n$ vertices and vertex subsets $A_1, A_2, ... A_k$, is it always the case that there is either a tree of size at most $\sqrt{n}$ that intersects every $A_i$, or a set $S$ of size at most $\sqrt{n}$ which intersects every such tree? (In other words, no connected component of $G-S$ intersects every $A_i$).
For the case of $k = 2$, this is implied by Menger's theorem. In fact, creating a larger graph with $k-1$ copies of $G$ and identifing the vertices in $A_i$ on the $i$ and $i+1$th layer shows that the bound is at most $\sqrt{(k-1)n}$. However, I haven't been able to get any better than that.
Does anyone know if this is true, or if this is unknown, what approaches I could take? I've tried searching online, but I haven't been able to find anything that helps.