Количество участников научного семинара равно 60 каждый из присутствующих знаком по крайней мере с 30 участниками в конце семинара пойдет игра для которой нужно найти хотя бы 1 команду из 4 человек посадить за круглый стол так чтобы каждый сидел рядом со знакомым человеком докажи что такую команду возможно найти

Задача в терминах графов: Пусть есть граф G с 60 вершинами (участниками), где каждая вершина имеет степень не меньше 30 (то есть каждый знает не менее 30 участников). Нужно доказать, что в G есть цикл длиной 4 (4 человека вокруг круглого стола так, чтобы каждый сидел рядом со знакомым). Доказательство по шагам: 1) Рассмотрим два варианта. - Вариант A: найдутся две вершины x и y, которые не смежны (не знакомы). - Вариант B: пар любых двух вершин не существует, то есть граф G полноценно-смежный, т. е. G = K60. В таком случае легко можно выбрать любую четвёрку вершин и из них составить круг из соседних пар — в полном графе есть множество четырехугольников, в том числе и C4. Значит, случай B нас удовлетворяет условиям задачи. Осталось рассмотреть вариант A, который реализует доказательство конструктивно. 2) Если x и y неAdjacent, то рассмотрим множества их соседей: N(x) — множество соседей вершины x, N(y) — множество соседей вершины y. По условию deg(x) ≥ 30 и deg(y) ≥ 30, значит |N(x)| ≥ 30 и |N(y)| ≥ 30. Так как все вершины различны x и y и всего их окружение находится в V \ {x, y}, то |N(x) ∪ N(y)| ≤ 58. По формуле включений-исключений: |N(x) ∩ N(y)| = |N(x)| + |N(y)| − |N(x) ∪ N(y)|. Минимум слева |N(x) ∩ N(y)| ≥ минимальное possible |N(x)| + |N(y)| − 58. Но минимальная сумма |N(x)| + |N(y)| равна 30 + 30 = 60. Следовательно, |N(x) ∩ N(y)| ≥ 60 − 58 = 2. Значит у x и y есть по меньшей мере два общих соседа, пусть это будут u и v, причем u ≠ v и u, v ∈ N(x) ∩ N(y). 3) Теперь образуем четверку x, u, y, v и посмотрим на ребра между ними: - x и u соседние (u ∈ N(x)), - u и y соседние (u ∈ N(y)), - y и v соседние (v ∈ N(y)), - v и x соседние (v ∈ N(x)). Следовательно, существуют ребра x–u, u–y, y–v, v–x. Эти четыре вершины образуют цикл длины 4: x − u − y − v − x. Таким образом, в случае A найдётся зацепка в виде четырехугольника, то есть искомая команда из 4 участников, сидящих вокруг круглого стола так, чтобы каждый сидел рядом со знакомым. 4) Применение к нашему случаю завершено. Итого: либо граф G уже содержит C4 (и значит есть требуемая команда), либо граф G не содержит C4, но тогда противоречие: в таком случае две непересекающиеся вершины имели бы по меньшей мере 2 общих соседа, что уже привело к существованию C4. Либо граф полноценно-смежный, что тоже дает возможность выбрать четыверку для круга. Значит такая команда обязательно существует.