Паросочетания и лемма Холла

Лемма. В графе степени всех вершин лежат в промежутке Тогда можно стереть несколько ребер так, что все степени будут лежать в промежутке

Доказательство. Достаточно доказать лемму для Давайте рассмотрим множество вершин такое, что в нём каждая вершина имеет степень Будем убирать ребра, которые внутри Вершины, у которых степень становится меньше убираем из множества Теперь рассмотрим все оставшиеся вершины и заметим, что выполняется условие теоремы Холла для множества и множества оставшихся вершин. А значит, есть какое-то паросочетание из в множество оставшихся вершин, которое покроет все вершины из Осталось удалить все эти ребра и понять, что максимальная степень стала а минимальная уменьшилась не более чем на один в последнем удалении.

_________________________________________________________________________________________________________________________________________________________________________________

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