Как доказать корректность алгоритма Куна через теорему Бержа об увеличивающих путях?

Увеличивающий путь для паросочетания $M$ — это простой путь, который начинается и заканчивается в непокрытых (свободных) вершинах и чередует рёбра «не в $M$ / в $M$ / не в $M$ / ...». Если такой путь есть, его можно «инвертировать» (поменять статус каждого ребра вдоль пути) — рёбер из $M$ станет на 1 больше.

Теорема Бержа: паросочетание $M$ максимально тогда и только тогда, когда в графе нет увеличивающего пути относительно $M$.

Набросок доказательства. ($\Rightarrow$) Если увеличивающий путь есть, инвертируем его и получаем большее паросочетание — значит $M$ не было максимальным. ($\Leftarrow$) Пусть $M$ не максимально, и есть большее $M'$. Рассмотрим симметрическую разность $M \oplus M'$ — она состоит из путей и циклов, где рёбра $M$ и $M'$ чередуются. Так как $|M'| > |M|$, найдётся путь, где рёбер $M'$ больше — а это и есть увеличивающий путь относительно $M$. Противоречие.

Корректность Куна. Кун, обрабатывая левые вершины по очереди, для каждой ищет увеличивающий путь (DFS, чередующий свободные рёбра и рёбра паросочетания). Он находит увеличивающий путь всякий раз, когда тот существует для текущей вершины. По завершении внешнего цикла ни для одной свободной левой вершины увеличивающего пути нет → по Бержу паросочетание максимально.

Ключевой факт, почему достаточно одного прохода по левым вершинам: однажды покрытая левая вершина остаётся покрытой до конца (паросочетание только растёт), поэтому пересматривать её не нужно.