Изменения

Рассмотрим паросочетание <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> этот путь является увеличивающей (дополняющей) цепью.

}}

== Источники информации ==