Dado un grafo $G$ $n$ vértices vértices y subconjuntos $A_1, A_2, ... A_k$, es siempre el caso de que no es un árbol de tamaño en la mayoría de las $\sqrt{n}$ que cruza todas las $A_i$, o un conjunto $S$ del tamaño en la mayoría de los $\sqrt{n}$ que se cruza cada árbol? (En otras palabras, no hay componente conectado de $G-S$ cruza todas las $A_i$).
Para el caso de $k = 2$, esto es implícita por Menger del teorema. De hecho, la creación de un gráfico de mayor tamaño con $k-1$ copias de $G$ y la identificación de los vértices en $A_i$ $i$ $i+1$th capa muestra que el obligado es en la mayoría de las $\sqrt{(k-1)n}$. Sin embargo, no he sido capaz de hacer nada mejor que eso.
¿Alguien sabe si esto es cierto, o si es desconocido, lo que los enfoques que puedo tomar? He tratado de buscar en internet, pero no he sido capaz de encontrar nada que le ayuda.
