|
|
 |
Условие
Назовём компанию k-неразбиваемой, если при любом разбиении её на k групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.
Решение
Каждой компании соответствует граф, в котором вершины соответствуют людям, а рёбра – знакомствам. Компания k-разбиваема, тогда и только тогда, когда вершины этого графа можно правильно окрасить в k цветов (так, чтобы соседние вершины имели разные цвета).
Лемма. Пусть в графе нет циклов нечётной длины. Тогда его вершины можно правильно раскрасить в два цвета.
Доказательство. Ясно, что достаточно доказать лемму для связного графа. Расстоянием между двумя вершинами X и Y назовём наименьшую длину пути, соединяющего эти вершины.
Зафиксируем некоторую вершину A и окрасим все вершины, находящиеся на нечётном расстоянии от A, в красный цвет, а остальные – в синий. Докажем, что указанная раскраска – искомая. Предположим, имеется ребро, соединяющее, скажем, синие вершины B и C. Рассмотрим кратчайшие пути A = B0, B1, ..., B2n = B и A = C0, C1, ..., C2m = C, ведущие из A в B и в C. Взяв наибольший индекс i, при котором Bi = Ci, получим цикл нечётной длины Bi, Bi+1, ... , B2n, C2m, C2m–1, ..., Ci = Bi. Противоречие.
По лемме в графе нашей компании есть нечётный цикл (иначе его вершины можно окрасить даже в два цвета). Выберем нечётный цикл C минимальной длины n. Тогда не существует рёбер, соединяющих вершины этого цикла, кроме рёбер самого цикла. Действительно, такое ребро разбило бы цикл на два меньших по длине, и один из них был бы нечётным.
Покажем, что любая вершина x, не принадлежащая C, соединена не более, чем с двумя вершинами C. Если n = 3, то это верно: по условию четыре человека – x и вершины C – не могут быть попарно знакомы.
Пусть n > 3. Предположим, что x соединена с вершинами v1, v2, v3 этого цикла. Участок цикла между какими-то двумя из них (скажем, между v1 и v2) содержит нечётное количество d рёбер. Если d < n – 2, то этот участок вместе с вершиной x образует нечётный цикл длины d + 2 < n, что невозможно. Значит, d = n – 2, то есть вершины v1, v3, v2 идут в цикле подряд. Но тогда v1, v3 – участок "длины" 1, а этот случай уже разобран.
Теперь мы можем предъявить требуемое разбиение: поместим в одну группу вершины цикла C, а в другую (назовём её D) – все остальные. Вершины цикла C, очевидно, нельзя правильно окрасить в два цвета. Осталось показать, что какие-то две вершины группы D соединены ребром. Предполагая противное, покажем, что весь граф можно окрасить в три цвета. Сначала окрасим все вершины C, кроме одной, попеременно в цвета 1 и 2, а оставшуюся – в цвет 3; поскольку между этими вершинами нет других рёбер, раскраска C – правильная. Окрасим теперь вершины группы D. Каждая очередная вершина соединена не более чем с двумя вершинами из C и не соединена с вершинами из D; значит, можно выбрать для неё цвет, отличный от цветов её соседей.
