Теорема Менгера: минимальное число вершин, разъединяющих вершины $s$ и $t$ в графе $G$, равно максимальному числу внутренне вершинно-непересекающихся путей между $s$ и $t$. Для $K_{3,3}$ (с долями $\{a_1,a_2,a_3\}$ и $\{b_1,b_2,b_3\}$): для любых двух несмежных вершин, например $a_1$ и $a_2$, существуют 3 внутренне непересекающихся пути: $a_1 - b_i - a_2$ для $i=1,2,3$. Поэтому минимальная $a_1$–$a_2$-разделяющая вершинная отсечка имеет размер не менее 3. Так как $\delta(K_{3,3})=3$ и $\kappa \leq \delta = 3$, то $\kappa(K_{3,3})=3$.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!