Дружба, но не сырок

[Ktina]

В классе 30 учеников, причём каждый дружит не менее, чем с 23 другими. Можно ли утверждать, что найдутся 5 учеников, которые все дружат между собой?

[iou]

Можно.
Рассмотрим граф знакомств, вершины которого $e_1, ~\cdots, ~ e_{30}$. Пусть $\deg e_i = 23 ~~ \forall i \in \{1, ~\cdots, ~30\}$
Без потери общности считаем, что вершина $e_{30}$ соединена с первыми $23$-мя вершинами, рассмотрим подграф на этих $23$-х вершинах. В худшем случае $\deg e_i = 16 ~~ \forall i \in \{1, ~ \cdots, ~23\}$ [то есть каждая вершина из подграфа соединена с $e_i ~~ \forall i \in \{24, ~ \cdots, ~30\}$]. В этом подграфе нужно найти полный подграф на $4$-х вершинах. Проделаем этот процесс еще $2$ раза, разность между количеством вершин подграфа и степенями вершин постоянна и равна $7$ (в худшем случае), в итоге получим граф на $9$-ти вершинах, степень каждой вершины $2$, в нём нужно найти полный подграф на двух вершинах, это возможно.

[Ktina]

iou
Большое спасибо!

-- 23.07.2017, 23:31 --

Если 23 заменить на меньшее целое число, ответ изменится?

[svv]

Говорят, изменится.
В исходной задаче у Вас граф с числом вершин $n=30$, минимальная степень вершины $\delta=23$. Надо доказать, что в графе существует клика (жуткое слово) размера $r=5$.

Я нашёл статью The Clique Algorithm индийского математика Ashay Dharwadker. Он показывает, что:
$\bullet$ в графе с $n$ вершинами и минимальной степенью вершины $\delta$ есть клика размером по крайней мере $\lceil \frac n{n-\delta}\rceil$;
$\bullet$ это утверждение нельзя усилить, в том смысле, что существует граф с заданными $n$ и $\delta$, у которого размер максимальной клики равен точно $\lceil \frac n{n-\delta}\rceil$.
Последнее доказывается явным построением такого графа (янепроверял).

Получается, что:
$\bullet$ любой граф с $n=30$ и $\delta=23$ имеет клику размера $5$;
$\bullet$ существует граф с $n=30$ и $\delta=22$ с максимальной кликой $4$.

[iou]

Да, изменится.
Предположим, что любой граф с заданными условиями ($30$ вершин, степень каждой вершины не меньше $22$-х) содержит полный подграф на пяти вершинах. Тогда рассмотрим произвольный граф с $30$-ю вершинами, причём степень каждой ровно $22.$ Тогда из предположения следует, что в этом графе всегда есть подграф на $22$-ух вершинах (причём степень каждой вершины не меньше $14$-ти), который содержит полный подграф на четырех вершинах. Из предположения следует, что такой подграф всегда имеет подграф на $14$-ти вершинах (причём степень каждой вершины не меньше $6$-ти), который содержит полный подграф на трёх вершинах.
То есть из предположения, в частности, следует, что произвольный граф на $14$-ти вершинах, у которого все вершины имеют степень $6$, содержит "треугольник", то есть полный подграф на трёх вершинах.
Это не так. Рассмотрим $K_{7, 7}$ и произвольную биекцию между вершинами разных долей. Получим $7$ пар вершин, тогда будем удалять те ребра графа, которые соответствуют этим парам, получим граф на $14$-ти вершинах, степень каждой которого в точности равна $6$-ти. В этом графе нет "треугольников", поскольку любые две соединенные вершины лежат в разных долях; из этого следует, что если бы существовала вершина, которая была бы соединена с этими двумя вершинами, то она бы лежала сразу в двух долях, но таких вершин нет.