4
$\begingroup$

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.

1 Answers 1

1

Unfortunately, it turns out the answer is no. For example, a $k-1$ dimensional simplex grid with sides of length $x$ has ${x+k-2}\choose{k-1}$ vertices with a minimum spanning tree of size $x$ and a minimum seperating set of size ${x+k-3}\choose{k-2}$. The product of these is approximately $(k-1)n$, meaning that the trivial bound is also tight. In particular, for $k=3$, it is impossible to do better than $\sqrt{2n} - \frac{1}{2}$.