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

Рассмотрим максимальное паросочетание, пусть в нём вершин. Любая из оставшихся вершин может быть соединена ребром лишь с вершинами паросочетания, причём из различных оставшихся вершин не могут вести рёбра в различные вершины пары (иначе ребро в паросочетании можно заменить на два). Так как в минимальном рёберном покрытии из каждой не входящей в паросочетание вершины выходит хотя бы по ребру, выделим сперва ровно по одному такому, их получилось рёбер. Теперь заметим, что для этого рёберного покрытия существует также минимальное рёберное покрытие, которое помимо выделенных рёбер содержит лишь рёбра паросочетания.

Допустим, есть какое-то меньшее реберное покрытие. Назовём ребром если оно соединяет какие-то вершины из паросочетания. Посмотрим, как покрыты вершины из паросочетания. Допустим, вершина в паре с Тогда пусть вершина накрыта ребром, которое торчит наружу из паросочетания и никаким из торчащих внутрь(иначе внутренних ребёр покрытия хотя бы столько же, сколько в паросочетании, победа). Посмотрим на вершину Она покрыта не соответствующим ребром паросочетания (из выбора ), при этом её ребро не торчит наружу. Допустим, она покрыта ребром в Рассмотрим Если из неё есть ребро наружу, то мы можем увеличить начальное паросочетание (взяв ребро в с ребром из неё). Получаем, что опять ребро идёт куда-то дальше. Когда-нибудь цикл замкнётся. Тогда мы накрыли вершин паросочетания внутренними рёбрами (наружу ведь выйти нельзя!), что даёт нужную нам оценку на внутренних рёбер в покрытии.

Таким образом, существует минимальное рёберное покрытие из рёбер и ещё рёбер паросочетания. Итого, сумма числа рёбер в максимальном паросочетании и числа рёбер в минимальном покрытии действительно равна