В стране провели анкету, в которой требовалось назвать своего любимого писателя, художника и композитора. Оказалось, что каждый упомянутый хоть раз деятель искусств является любимых не более чем k человек. Обязательно ли всех проанкетированных можно разделить на не более чем 3k-2 группы, чтобы в каждой группе любые два человека имели абсолютно разные вкусы.
Введём граф, вершинами будут опрашиваемые люди. Соединим две вершины ребром, если у соответствующих людей один любимый писатель, любимый художник или любимый композитор. Тогда из каждой вершины выходит не более 3(k-1)=3k-3 ребра.
Докажем теперь такую лемму:
если в графе у каждой вершины степень не более m, то можно раскрасить вершины этого графа в m+1 цвет так, что вершины одного цвета не будут соединены. (Степенью вершины называется число рёбер, которые выходят из этой вершины.)
Из этой леммы для m=3k-3 следует утверждение задачи, если мы в каждую группу поместим все вершины какого-то цвета.
Доказательство леммы проведём по индукции по числу вершин. База для n=1 вершины очевидна, ибо такой граф мы точно можем раскрасить, используя не более m цветов.
Пусть теперь утверждение леммы верно при n=s. Докажем его при n=s+1. Рассмотрим в графе с s+1 вершинами ту, у которой максимальная степень, и удалим её вместе со всеми выходящими из неё рёбрами. Получим граф, у которой максимальная степень также не превосходит m, но теперь у него всего s вершин. По предположению индукции такой граф можно раскрасить в m+1 цвет. Но тогда вершины, соседние с удалённой, использовали не более m цветов (потому что их самих не более m). Значит, мы могли покрасить удалённую вершину в оставшийся (m+1)-й цвет.
На самом деле, обычно можно раскрасить не в (m+1), а в m цветов. Это утверждение носит название теоремы Брукса. Она гласит, что так можно сделать всегда, кроме двух случаев:
1) m=2 и граф G имеет компоненту, являющуюся нечётным циклом;
2) m>2 и одна из компонент графа G - полный подграф на m+1 вершине.