Задача
COM-B1-M09-P020 Одиннадцать вершин
#20
★★★☆☆ Уровень 3 из 5
Докажите, что граф на \(11\) вершинах, в котором степень каждой вершины не меньше \(6\), связен.
В маленькой компоненте степень не может быть большой.
Если граф несвязен, возьмем одну компоненту. Если ее размер не больше \(6\), то степень любой вершины в ней не больше \(5\), противоречие. Значит каждая компонента должна иметь хотя бы \(7\) вершин. Но две такие компоненты уже содержали бы хотя бы \(14\) вершин, больше чем \(11\). Поэтому компонент больше одной быть не может, граф связен.
Типовой компонентный аргумент.