Верное утверждение (теорема Уитни): для любого графа $\kappa(G) \leq \lambda(G) \leq \delta(G)$, где $\kappa$ — вершинная связность, $\lambda$ — рёберная связность. Таким образом, $\kappa(G) \leq \delta(G)$, а не равенство. Доказательство неравенства $\kappa \leq \delta$: у вершины минимальной степени $v$ есть ровно $\delta$ соседей; удаление всех $\delta$ соседей изолирует $v$, поэтому $\kappa(G) \leq \delta(G)$. Равенство не всегда достигается: например, $K_{2,3}$ имеет $\delta=2$, но $\kappa=2$ — здесь совпадение; тогда как у некоторых графов $\kappa < \delta$.

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