Выделите одну вершину из 17 и попробуйте свести задачу к
.
Кли́ка.
Спасибо. Давайте использовать синий, красный, зеленый цвета.
Среди 16 ребер из
вершины найдутся 6 одноцветных ребер, согласно принципу Дирихле. Пусть нашлись 6 синих ребер к вершинам
.
Возможны две ситуации :
1) Среди вершин
нет тех, что соединены синими ребрами, тогда найдется красный треугольник или зеленый, так как
.
2) Есть хотя бы одно ребро, соед две вершины из
. Тогда
и эти две вершины образуют синий треугольник.
То есть доказано, получается, что
, но как доказать ,что
?