Изменения
→Теорема о максимальном паросочетании и дополняющих цепях
В доказательстве используются несколько новых понятий:
{{Определение
|definition= '''Увеличивающая цепь ''' - чередующаяся цепь, у которой оба конца свободны.}}
{{Определение
|definition= '''Уменьшающая цепь ''' - чередующаяся цепь, у которой оба конца покрыты.}}
{{Определение
|definition= '''Сбалансированная цепь ''' - чередующаяся цепь, у которой один конец свободен, а другой покрыт}}
Рассмотрим паросочетание <tex>M</tex> в графе <tex>G</tex> и предположим, что <tex>M</tex> - не наибольшее. Докажем, что тогда имеется увеличивающая цепь относительно <tex>M</tex>. Пусть <tex>M'</tex> - другое паросочетание и <tex>|M'|>|M|</tex>. Рассмотрим подграф <tex>H</tex> графа <tex>G</tex>, образованный теми ребрами, которые входят в одно и только в одно из паросочетаний <tex>M</tex>, <tex>M'</tex>. Иначе говоря, множеством ребер графа <tex>H</tex> является симметрическая разность <tex>M\oplus M'</tex>. В графе <tex>H</tex> каждая вершина инцидентна не более чем двум ребрам (одному из <tex>M</tex> и одному из <tex>M'</tex> ), т.е. имеет степень не более двух. В таком графе каждая компонента связности - путь или цикл. В каждом из этих путей и циклов чередуются ребра из <tex>M</tex> и <tex>M'</tex>. Так как <tex>|M'|>|M|</tex>, имеется компонента, в которой ребер из <tex>M'</tex> содержится больше, чем ребер из <tex>M</tex>. Это может быть только путь, у которого оба концевых ребра принадлежат <tex>M'</tex>. Заметим, что относительно <tex>M</tex> этот путь является увеличивающей (дополняющей) цепью.
