Изменения
→Теорема Эдмондса
Рассмотрим отдельно случай, когда <tex>P</tex> начинается со сжатого соцветия <tex>B'</tex>, т.е. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины <tex>v</tex>. Учитывая всё вышесказанное, получаем, что путь <tex>P_1(b,...v,...c,..)</tex> является увеличивающим путём в графе <tex>G</tex>.
Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B'</tex>, но не начинается и не заканчивается в ней. Тогда в <tex>P</tex> есть два ребра, проходящих через <tex>B'</tex>, пусть это <tex>(a,B')</tex> и <tex>(B',c)</tex>. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка насыщены рёбрами цикла, то мы приходим к противоречию (это эквивалентно [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|случаю отсутствия ребра из <tex>R_R^-</tex> в <tex>L_L^+</tex>]]). Таким образом, этот случай просто невозможен. Теорема доказана.
}}
