Решение задачи 495

Условие:

У каждого из жителей некоего города есть три знакомых жителя, причём с одним из них он активно общается каждое утро, с другим — каждый полдень, с третьим — каждый вечер. Петя с Васей поссорились и прекратили общаться. Петя заразился вирусом. Докажите, что Вася тоже вскоре заразится.

Решение:

Перейдем на язык графов: люди -- вершины, общение -- ребра. Тогда задача формулируется так:

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

Рассмотрим все зеленые ребра в первой компоненте связности. Они не пересекаются и покрывают все вершины компоненты (очевидно, что нет зеленых ребер, соединяющих точки из разных компонент). Отсюда следует, что в первой компоненте четное число вершин.

Рассмотрим множество вершин первой компоненты без вершины А. В этом множестве четное число вершин, так как оно покрывается красными непересекающимися ребрами. Значит, в первой компоненте нечетное число вершин, противоречие с предыдущим абзацем.

Получается, граф не распадается на две компоненты, или, другими словами, Вася вскоре заразится.