Изменения
→Теорема Эдмондса
Пусть даны граф <tex>G</tex>, паросочетание <tex>M</tex> в <tex>G</tex> и цикл <tex>Z</tex> длины <tex>2k+1</tex>, содержащий <tex>k</tex> рёбер паросочетания <tex>M</tex> и вершинно непересекающийся с остальными рёбрами из <tex>M</tex>. Построим новый граф <tex>G'</tex> из графа <tex>G</tex>, сжимая цикл <tex>Z</tex> до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание <tex>M -E(Z)</tex>, где <tex>E(z)</tex> {{---}} ребра, инцидентные циклу, является наибольшим в <tex>G'</tex> тогда и только тогда, когда М {{---}} наибольшее паросочетание в <tex>G</tex>
|proof=
Предположим, что <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, тогда в силу [[Теорема о максимальном паросочетании и дополняющих_цепях|теоремы о максимальном паросочетании и дополняющих цепях]] существует увеличивающая относительно <tex>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>Z</tex>, то цепь является увеличивающей относительно <tex>M'</tex> и в графе <tex>G'</tex>, а значит, <tex>M'</tex> не может быть наибольшим паросочетанием. Поэтому предположим, что цепь <tex>P</tex> пересекается с <tex>Z</tex>. Заметим, что хотя бы одна концевая вершина цепи <tex>P</tex> не лежит на <tex>Z</tex>, обозначим её через <tex>u</tex>. Тогда пройдём по цепи <tex>P</tex>, начиная с <tex>u</tex> до первой встречной вершины на <tex>Z</tex>, обозначим её через <tex>v</tex>. Тогда, при сжатие сжатии цикла <tex>Z</tex>, участок <tex>P[u,v]</tex> отобразится на увеличивающую цепь относительно <tex>M'</tex>, то есть <tex>M'</tex> не является максимальным паросочетанием, что противоречит нашему предположению.
Теперь допустим, что <tex>M'</tex> не является наибольшим паросочетанием в графе <tex>G'</tex>. Обозначим через <tex>N'</tex> паросочетание в <tex>G'</tex>, мощности большей, чем <tex>M'</tex>. Восстановим граф <tex>G</tex>, тогда <tex>N'</tex> будет соответствовать некоторому паросочетанию в <tex>G</tex>, покрывающему не более одной вершины в <tex>Z</tex>. Следовательно паросочетание <tex>N'</tex> можно увеличить, используя <tex>k</tex> рёбер цикла <tex>Z</tex>, и получить паросочетание <tex>N</tex>, размера <tex>|N| = |N'|+k > |M'|+k = |M|</tex>, то есть <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, приходим к противоречию. Таким образом теорема доказана.
