Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.