Изменения

1) A Последовательно удаляя вершины множества <tex> A = A(G)D </tex>, по лемме о стабильности мы получим:* <tex>D(G − - A) = D(G), </tex> * <tex>A(G − - A) = ∅\O, </tex>* <tex>C(G − - A) = C(G),</tex>α* <tex>\alpha (G − - A) = α\alpha (G) − - |A|.Это означает, что не существует рјберD соединяющих вершины из C(G − A) и D(G − A). Каждое максимальное паросочетание M' графа G - A покрывает все вершины множества C(G), поэтому M' содержитсовершенное паросочетание графа C. Тем самым, мы доказали пункт 1).</tex>

2Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A) Из формулы α</tex> и <tex>D(G − - A) = α</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G - A</tex> покрывает все вершины множества <tex>C(G) − |A|. следуетD что U1</tex>,поэтому <tex>M'</tex> содержитсовершенное паросочетание графа <tex>C</tex>..Тем самым,Un- компоненты связности графа G − Aмы доказали пункт 1). Для любой вершины u \in Ui существует максимальное

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> (разумеетсяD разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, α<tex> \alpha (Di) = α\alpha (Di - u) </tex> и по теореме 2.12 мы получаем, что граф <tex>Di </tex> - фактор-критический.