Раскраска ребер графа

Задача 5. В работе международного симпозиума лингвистов участвуют   человек. Из любых четырех один может объясняться с остальными тремя хотя бы на одном языке. Нужно доказать, что найдется участник симпозиума, который может объясниться с каждым из остальных участников.

Решение. Имеем полный граф с   вершинами и ребрами двух цветов (синее ребро — двое могут объясниться на каком-нибудь языке, красное — не могут). По условию, среди любых четырех вершин графа всегда найдется, по меньшей мере, одна, синяя степень которой равна трем.

Случай, когда все  ребра синие, тривиален, математически  неинтересен. Пусть найдется красное  ребро  . Добавим еще какие-нибудь две вершины  . Из четырех вершин   найдется хотя бы одна синяя, степень которой равна трем. Это   или  . Пусть, например, синюю степень три имеет  . Добавим еще одну вершину —  . Из вершин   или   или   имеет синюю степень, равную трем. В обоих случаях   соединена синим ребром с  . Переберем все вершины. В итоге окажется, что   соединена синим ребром со всеми вершинами графа. Во всякой четверке вершин, включая   и  , есть вершина, соединенная синим ребром со всеми остальными вершинами графа. Отсюда, кроме   и  , существует самое большее одна вершина, не соединенная синим ребром со всеми остальными.

Задача  о несцепленных треугольниках с одноцветными сторонами

Задача 6. Назовем группу людей "однородной", если любая пара из этой группы психологически совместима или, напротив, любая пара психологически несовместима. Нужно доказать, что среди восьми случайно встретившихся незнакомцев всегда найдутся две однородные группы, состоящие из трех человек каждая, причем никто из первой группы не входит во вторую.

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

Решение. Рассмотрим в графе один из треугольников   с одноцветными сторонами. По теореме 3, такой треугольник всегда найдется. Если остальные пять вершин и ребра, соединяющие их попарно, содержат еще один треугольник с одноцветными сторонами, то он и будет являться вторым искомым треугольником. (Для этого случая задача решена.) Если остальные пять вершин   не содержат треугольника с одноцветными сторонами, то они образуют пятиугольник с красными сторонами и синими диагоналями. На рисунке (рис. 1) изображены не все ребра графа, соответствующего задаче, а лишь треугольник   с красными сторонами и пятиугольник   с красными сторонами и синими диагоналями.

Покажем, что если какая-нибудь вершина треугольника   соединена синими ребрами с двумя вершинами пятиугольника, через одну, например   с   и   (рис. 2), то найдется еще один треугольник с одноцветными сторонами, не сцепленный с треугольником  .

Действительно, обратим  внимание на пятиугольник  . Если он содержит треугольник с одноцветными сторонами, то второй треугольник с одноцветными сторонами, не сцепленный с первым, найден. Если не содержит, то ребра   — красные, поскольку ребра  , по свойству 3 — уже синие. То есть образован треугольник   с красными сторонами, не сцепленный с треугольником   (рис. 3).

Остается рассмотреть  случаи, когда каждая вершина треугольника   соединена красными ребрами, по меньшей мере, с тремя последовательными вершинами пятиугольника  . Тогда у пятиугольника найдутся две вершины, каждая из которых соединена красными ребрами с двумя вершинами треугольника  . На (рис. 4) и (рис. 5) показаны все такие случаи. На (рис. 1.) легко обнаружить два несцепленных треугольника   и  . А на (рис. 5) хотя бы одно из ребер   должно быть красным (иначе вершина   будет соединена синими ребрами с двумя вершинами пятиугольника  , взятыми через одну, а этот случай уже рассмотрен).

Если хотя бы одно из ребер   или   — красное, то появятся треугольники   и   или треугольники   и   с красными сторонами. Таким образом, во всех случаях найдутся два несцепленных треугольника с одноцветными сторонами. Задача решена и установлено еще одно свойство.

Свойство 6. В полном графе с восемью вершинами, ребра которого окрашены в два цвета, обязательно найдутся два треугольника с одноцветными сторонами, которые не являются сцепленными.