Задача
COM-B1-M09-P017 Минимальная степень \(3\)
#17
★★★☆☆ Уровень 3 из 5
Докажите, что граф на \(6\) вершинах, в котором степень каждой вершины не меньше \(3\), обязательно связен.
Если граф несвязен, рассмотрите компоненту с не более чем \(3\) вершинами.
Если граф несвязен, его вершины разбиваются как минимум на две компоненты. Одна из компонент имеет не более \(3\) вершин. Внутри такой компоненты любая вершина может быть соединена максимум с \(2\) другими вершинами, значит ее степень не больше \(2\). Это противоречит условию, что все степени не меньше \(3\).
Простой, но важный способ доказывать связность.