9. Ной должен разместить 8 видов животных в четырёх отсеках ковчега. Все отсеки должны быть заполнены. Известно, что для каждого вида животных имеется не более трёх других видов, с которыми они не могут находиться в одном помещении. Докажите, что можно разместить животных так, что в каждом отсеке будут находиться только «совместимые» виды.

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

Любой граф с максимальной степенью не более 3 допускает раскраску в 4 цвета: это следует из жадного алгоритма. Действительно, будем последовательно окрашивать вершины; при окрашивании очередной вершины запрещены цвета только её уже окрашенных соседей, которых не более трёх. Из четырёх цветов хотя бы один останется доступным.

Поместим животных одного цвета в один отсек. Внутри каждого отсека не будет несовместимых пар, поскольку соединённые вершины имеют разные цвета.

Если какой-либо цвет не используется, можно перенести в соответствующий пустой отсек одного или нескольких животных, сохранив совместимость; поскольку всего 8 животных и 4 отсека, распределение можно выбрать так, чтобы все отсеки были непустыми.

Что и требовалось доказать.