Изменения

# Путь Пусть путь из <tex>s</tex> в <tex>t</tex> является дополняющей цепью для исходного графа <tex>G</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепьютеоремы]] для исходного графа - если мы на каждом шаге можем найти новый путь, т.е. находим новую дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, то текущее паросочетание - искомое. Осталось доказать, что путь из <tex>s</tex> в <tex>Gt</tex>действительно является дополняющей цепью. Действительно, в  В этом пути два конца свободны, т.к. они не являются ребрами графа <tex>G</tex> и, значит, не входят в паросочетание. По построению графа <tex>G'</tex> этот путь содержит нечетное число ребер (т.к. в <tex>G'</tex> нет ребер из <tex>s</tex> в <tex>y \in R</tex>, а так же ребер из <tex>x \in L</tex> в <tex>t</tex>, то попасть из истока в сток можно только через какие-либо две вершины <tex>x \in L</tex> и <tex>y \in R</tex>, расстояние между которыми в двудольном графе (в ребрах) - нечетная величина). В таком случае ребра пути <tex>s-t</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные - покрытыми.# Инвертирование ребер не меняет пути, следовательно, он остается дополняющей цепью.# В найденном пути вершины не повторяются (это свойство поиска в глубину), тогда множество ребер, ведущих только из <tex>R</tex> в <tex>L</tex> является паросочетанием.# Путь не был найден. Это значит, что не существует дополняющей цепи Тогда этот путь - дополняющая цепь для графа <tex>G'</tex>. Тогда по [[Теорема о максимальном паросочетании и дополняющих цепях|теореме]] текущее паросочетание является максимальным.