Изменения

является дополняющей цепью для исходного графа <tex>G</tex> и обратно - т.е. любая дополняющая цепь графа <tex>G</tex> является путем <tex>p'</tex>. Тогда из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы]] — если мы на каждом шаге можем найти новый путь, т.е. находим новую дополняющую цепь, то мы увеличиваем текущее паросочетание. Если путь найти мы уже не можем, то значит дополняющих цепей в графе нет и текущее паросочетание — искомое. Осталось доказать, что путь <tex>p'</tex> действительно является дополняющей цепью.

Т.к. <tex>p'</tex> — путь в двудольном графе, он нечетной длины, в котором вершины не повторяются (т.к. этот путь строится с помощью поиска в глубину). Рассмотрим текущее паросочетание. Мы записывали в него ребра из <tex>L</tex> в <tex>R</tex>, но после этого инвертировали их. Значит, ребра текущего паросочетания сейчас ведут из <tex>R</tex> в <tex>L</tex>. В таком случае его ребра пути <tex>p'</tex> можно пронумеровать так, чтобы нечетные ребра были свободными, а четные — покрытыми(что соответствует текущему паросочетанию). Тогда этот путь — дополняющая цепь для графа <tex>G</tex>, ти паросочетание можно перезаписать.е. только ребра Обратно — дополняющая цепь в графе <tex>G</tex> это путь нечетной длины из <tex>L</tex> в <tex>R</tex> включаем . Он начинается в какой-то вершине <tex>u \in L\</tex> и заканчивается в паросочетание вершине <tex>v \in R\</tex> (что соответствует инварианту его построенияпоскольку концевые вершины этого пути должны быть свободны). Нo каждая вершина из <tex>L</tex> связана ребром с <tex>s</tex> в графе <tex>G'</tex>, аналогично каждая вершина из <tex>R</tex> связана ребром с <tex>t</tex>. Тогда этот путь — любая дополняющая цепь для графа в графе <tex>G</tex> является частью пути из <tex>s</tex> в <tex>t</tex> в графе <tex>G'</tex>, или, что то же самое, является путем <tex>p'</tex>. Отсюда следует, что алгоритм корректен.