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

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