Изменения
→Декомпозиция Эдмондса-Галлаи
тогда:
<br>
|proof=
1) Последовательно удаляя вершины множества<tex> A = A(G)</tex>, по лемме о стабильности мы получим:
2) Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U1,{...},Un</tex>- компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in Ui </tex>существует максимальное паросочетание <tex>Mu</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>Ui</tex> - компонента связности графа <tex>G - A</tex>, паросочетание <tex>Mu</tex> содержит максимальное паросочетание графа <tex>Di</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (Di) = \alpha (Di - u) </tex> и по теореме 2.12 мы получаем, что граф <tex>Di</tex> - фактор-критический.
3) Пусть <tex>M </tex> - максимальное паросочетание графа <tex>G</tex>, а <tex>M' </tex> полученоиз <tex>M </tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда<tex>|M'| ≥ \ge |M| − - |A| </tex> и по формуле α<tex> \alpha (G − - A) = α\alpha (G) − - |A| </tex> понятно, что <tex>M' </tex> - максимальноепаросочетание графа <tex>G − - A</tex>. Более того, из α<tex> \alpha (G − - A) = α\alpha (G) − - |A| </tex> следует <tex>|M'| = |M|−- |A|</tex>, а значит, все вершины множества <tex>A </tex> покрыты в <tex>M </tex> различными рёбрамию Так как <tex>M' </tex> - максимальное паросочетание графа <tex>G - A</tex>, то по пунктам 1) и 2) очевидно, что <tex>M' </tex> содержит совершенное паросочетание графа <tex>C </tex> и почти совершенные паросочетания фактор-критических графов <tex>D1,{...},Dn</tex>. Значит, рёбра паросочетания <tex>M </tex> соединяют вершины <tex>A </tex> с непокрытыми <tex>M' </tex> вершинами различных компонентсвязности из <tex>U1,{...},Un</tex>. 4) Из пункта 3) сразу же следуют оба равенства пункта 4).
