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