Предположим, граф несвязен. Тогда его можно разбить на две непустые части $A$ и $B$, между которыми нет рёбер. Если $|A| = k$, то $|B| = 6$ — $k$. Любая вершина из $A$ имеет степень не менее 3, но все её соседи тоже в $A$, поэтому $k$ — $1 \geq 3$, то есть $k \geq 4$. Аналогично для B: 6 — $k$ — $1 \geq 3$, то есть $k \leq 2$. Получаем $k \geq 4$ и $k \leq 2$ одновременно — противоречие. Следовательно, граф связен.

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