Номер 4.121, страница 130 - гдз по алгебре 10 класс учебник Шыныбеков, Шыныбеков

4.121. Докажите, что среди любых 9 человек найдутся трое, знакомых друг с другом, либо найдутся 4 человека, не знакомых друг с другом.

Эта задача относится к теории Рамсея. Давайте переформулируем ее на языке теории графов.

Представим 9 человек как 9 вершин полного графа $K_9$. Ребро между двумя вершинами будем красить в синий цвет, если соответствующие люди знакомы, и в красный цвет, если они не знакомы. Поскольку знакомство — это взаимное отношение, граф является неориентированным.

Задача сводится к доказательству следующего утверждения: любая 2-цветная раскраска ребер полного графа $K_9$ (синим и красным цветами) обязательно содержит либо синий треугольник ($K_3$), либо красный полный подграф на 4 вершинах ($K_4$).

• Синий $K_3$ представляет собой троих попарно знакомых людей.
• Красный $K_4$ представляет собой четверых попарно незнакомых людей.

Это утверждение эквивалентно доказательству того, что число Рамсея $R(3, 4) \le 9$.

Доказательство будем проводить от противного. Предположим, что существует такая раскраска ребер графа $K_9$, в которой нет ни синего $K_3$, ни красного $K_4$.

Рассмотрим произвольную вершину $v$ в этом графе. Она соединена с остальными 8 вершинами. Эти 8 ребер окрашены либо в синий, либо в красный цвет. Пусть $d_B(v)$ — количество синих ребер, инцидентных вершине $v$ (число знакомых у человека $v$), а $d_R(v)$ — количество красных ребер (число незнакомых). Очевидно, что $d_B(v) + d_R(v) = 8$.

Рассмотрим множество $N_B$ соседей вершины $v$, соединенных с ней синими ребрами.

В подграфе, порожденном вершинами из $N_B$, не может быть ни одного синего ребра. Если бы между какими-либо двумя вершинами $u, w \in N_B$ было синее ребро, то вершины $\{v, u, w\}$ образовывали бы синий треугольник $K_3$, так как ребра $(v, u)$ и $(v, w)$ синие по определению множества $N_B$. Это противоречит нашему исходному предположению.Следовательно, все ребра между вершинами в $N_B$ должны быть красными. Это означает, что подграф, порожденный $N_B$, является полным красным подграфом.

По нашему предположению, в графе нет красного $K_4$. Значит, в $N_B$ не может быть 4 или более вершин. Таким образом, размер множества $N_B$ не превышает 3, то есть $d_B(v) = |N_B| \le 3$.

Теперь рассмотрим множество $N_R$ соседей вершины $v$, соединенных с ней красными ребрами.

В подграфе, порожденном вершинами из $N_R$, не может быть красного треугольника $K_3$. Если бы такой треугольник $\{u, w, z\}$ существовал, то вершины $\{v, u, w, z\}$ образовывали бы красный $K_4$, поскольку $v$ соединена с каждой из этих вершин красным ребром. Это также противоречит нашему предположению.

Итак, в подграфе, порожденном $N_R$, нет красного $K_3$. В то же время, по основному предположению, в нем нет и синего $K_3$. Это означает, что подграф на вершинах из $N_R$ является 2-цветным графом без монохроматических треугольников.

Известно, что число Рамсея $R(3, 3) = 6$. Это означает, что любой полный граф на 6 или более вершинах при любой 2-цветной раскраске ребер содержит монохроматический $K_3$. Следовательно, количество вершин в $N_R$ должно быть строго меньше 6. Таким образом, $d_R(v) = |N_R| \le 5$.

Поскольку вершина $v$ была выбрана произвольно, эти выводы верны для любой вершины графа:

1. $d_B(v) \le 3$ для любой вершины $v$.

2. $d_R(v) \le 5$ для любой вершины $v$.

При этом для каждой вершины должно выполняться равенство $d_B(v) + d_R(v) = 8$. Единственный способ удовлетворить всем трем условиям одновременно — это если для каждой вершины $v$ в графе $K_9$ выполняются точные равенства: $d_B(v) = 3$ и $d_R(v) = 5$.

Если такое возможно, то рассмотрим подграф, состоящий только из синих ребер. Этот граф имеет 9 вершин, и степень каждой вершины в нем равна 3 (это 3-регулярный граф).

Согласно лемме о рукопожатиях (теореме о сумме степеней вершин), сумма степеней всех вершин в любом графе равна удвоенному числу его ребер и, следовательно, должна быть четным числом.

Вычислим сумму степеней вершин в нашем синем подграфе: $\sum_{v \in V} d_B(v) = 9 \times 3 = 27$.

Число 27 — нечетное. Это противоречит лемме о рукопожатиях. Следовательно, не может существовать графа на 9 вершинах, в котором степень каждой вершины равна 3.

Полученное противоречие означает, что наше первоначальное предположение о существовании раскраски $K_9$ без синего $K_3$ или красного $K_4$ было неверным. Таким образом, в любой группе из 9 человек обязательно найдется либо трое попарно знакомых, либо четверо попарно незнакомых.

Ответ: Утверждение доказано.