Задача
COM-B1-M09-P021 Минимальная степень \(5\)
#21
★★★★☆ Уровень 4 из 5
Докажите, что в графе на \(9\) вершинах, где степень каждой вершины не меньше \(5\), обязательно есть треугольник.
Возьмите вершину и посмотрите на ее соседей.
Возьмем вершину \(v\). У нее есть хотя бы \(5\) соседей. Если среди этих соседей есть ребро, то вместе с \(v\) получаем треугольник. Если ребер между соседями \(v\) нет, то каждый из этих соседей соединен с \(v\) и может быть соединен только с тремя вершинами, не входящими в множество соседей \(v\) и не равными \(v\). Тогда его степень не больше \(1+3=4\), что противоречит минимальной степени \(5\). Значит треугольник существует.
Хорошая первая экстремальная графовая задача.