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

1. Начинается с пустого паросочетания. 3
2. Ищутся увеличивающие цепи. 3 Для этого для каждой вершины из первой доли графа перебираются рёбра из неё. 3 Если ребро ведёт в свободную вершину, то увеличивающая цепь найдена. 3 Если вершина занята ребром из паросочетания, то по этому ребру переходят в первую долю и продолжают. 3
3. Если увеличивающую цепь найти не удаётся, процесс останавливают, текущее паросочетание и есть максимальное. 25

Для поиска увеличивающей цепи можно мысленно построить граф, в котором из правой доли в левую можно идти только по рёбрам паросочетания, а из левой в правую — по любым. 1 Тогда можно запустить поиск любого пути из свободной вершины левой доли в какую-нибудь свободную вершину правой доли в изменённом графе, и ровно такой путь и будет увеличивающим. 1