Изменения
→Декомпозиция Эдмондса-Галлаи
* <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>
}}
{{Теорема
|about=Галлаи
|statement=
<tex>G</tex> - фактор-критический граф <tex> \Leftrightarrow </tex> <br>
<tex>G</tex> - связен и для любой вершины<tex> u \in V(G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha (G)</tex>.
}}
{{Лемма
|about= (Галлаи, о стабильности)
|statement=
пусть <tex> a \in A(G).</tex> Тогда:
{{Теорема
|about = Галлаи, Эдмондс
|statement=
пусть дан граф G = (V, E).
совершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт 1).
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>.
