Задача 003 — Задачи на Графы

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

Подсказка

Предположите, что нечётного цикла нет. Что следует из двудольности?

Решение

Пусть данные важные ребра — $a b$ и $a c$ , а максимальный размер пустого подграфа — $k$ . Тогда есть такие множества вершин $B$ и $C$ мощности $k+1$ каждое, что $a b$ и $a c$ соответственно являются в них единственными ребрами. Выкинем из графа все вершины, кроме $B \cup C$ , от этого условие не изменится. После этого все вершины множества $B \cap C$ , кроме вершины $a$ , ни с какой вершиной не соединены. Поэтому их тоже можно выбросить, после чего как $k$ , так и количества элементов в $B$ и $C$ уменьшатся на одну и ту же величину. После этого у нас остался граф на $2 k+1$ вершине; если в нем нет нечетного цикла, то он двудольный, тогда в нем есть пустой подграф на $k+1$ вершине, что не так. Следовательно, нечетный цикл есть.