Задача 050

от

На балу присутствуют 2015 пар, составленных из мальчика и девочки. Каждый участник бала знаком со своим партнёром и ещё хотя бы с одним участником противоположного пола. Докажите, что всех участников можно покрасить в три цвета так, чтобы у каждого было хотя бы два разноцветных знакомых.

Подсказка

Пусть M_{1} D_{1}, \ldots, M_{2015} D_{2015} — наши пары. Каждую девочку D_{i} соединим с другой девочкой, знакомой с M_{i}. В результате получится граф на вершинах D_{1}, \ldots, D_{2015} с 2015 рёбрами.

Решение

Пусть M_{1} D_{1}, \ldots, M_{2015} D_{2015} — наши пары. Каждую девочку D_{i} соединим с другой девочкой, знакомой с M_{i}. В результате получится граф на вершинах D_{1}, \ldots, D_{2015} с 2015 рёбрами. Нам нужно покрасить этот граф правильным образом в три цвета, это и будет искомая покраска девочек. Рассмотрим компоненту связности построенного графа, пусть в ней n вершин, тогда и рёбер в ней тоже n (Мы провели по одному ребру из каждой вершины этой компоненты связности, из вершин вне компоненты рёбра в нее не входят). Если есть вершина степени 1 , удалим ее, эту вершину можно будет легко докрасить после покраски остальных вершин компоненты. После серии таких операций наша компонента связности будет иметь минимальную степень вершины 2 , а значит, это будет простой цикл, который мы легко покрасим в три цвета.