Теорема о свадьбах

Лемма Холла, также известная как теорема о свадьбах — очень удобный критерий в задачах, где нужно проверить, что паросочетание существует, но при этом не требуется строить его явно.

Лемма Холла. Полное паросочетание существует тогда и только тогда, когда любая группа вершин левой доли соединена с не меньшим количеством вершин правой доли.

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

В другую сложнее — нужно воспользоваться индукцией. Будем доказывать, что если паросочетание не полное, то можно в таком графе найти увеличивающую цепь, и с её помощью увеличить паросочетание на единицу.

База индукции: одна вершина из $L$, которая по условию соединена с хотя бы одной вершиной из $R$.

Индукционный переход: пусть после $k < n$ шагов построено паросочетание $M$. Докажем, что в $M$ можно добавить вершину $v$ из $L$, не насыщенную паросочетанием.

Рассмотрим множество вершин $H$ — все вершины, достижимые из $x$, если можно ходить из правой доли в левую только по рёбрам паросочетания, а из левой в правую — по любым (мы такой граф по сути строим, когда ищем увеличивающую цепь в алгоритме Куна)

Тогда в $H$ найдется вершина $y$ из $R$, не насыщенная паросочетанием. Иначе, если такой вершины нет, то получается, что если рассмотреть вершины $H_L$ (вершины левой доли, насыщенные паросочетанием), то для них не будет выполнено условие, что $|H_L| \leq |N(H_L)|$ (здесь $N(X)$ — множество вершин, соединенным паросочетанием с $X$).

Тогда должен существовать путь из $x$ в $y$, и он будет увеличивающим для паросочетания $M$, потому что из $R$ в $L$ мы всегда шли только по ребрам паросочетания. Проведя чередование вдоль этого пути, получим большее паросочетание, следовательно предположение индукции верно.