Изменения

<tex>\mathrm{ \alpha} (G) = \min\limits_{U \in V} \{\dfrac{1}{2}(|V|+|U|-\mathrm{odd}(G - U)\}. </tex>|proof=Предположим <tex>G</tex> {{---}} связный (формула аддитивности). Докажем по индукции для количества вершин. <br>База: одна вершина {{---}} тривиально. <br>Шаг (рассмотрим два случая):# <tex>G</tex> {{---}} содержит вершину <tex>v</tex> покрытую всеми максимальными паросочетаниями (например средняя вершина)#: Тогда <tex> \mathrm{\alpha}(G - v) = \mathrm{\alpha}(G) - 1 </tex>.#: По индукции, формула Тутта-Бердже содержит <tex>G - v</tex> для некоторого множества <tex>U'</tex>.#: Пусть <tex>U = U' \bigcup v</tex>. Тогда:#: <tex> \mathrm{\alpha}(G) = \mathrm{\alpha}(G - v) + 1 = \dfrac{1}{2}(|V - v|+|U - v| - \mathrm{odd}(G - v - (U - v))) + 1 = </tex>#: <tex> = \dfrac{1}{2}(|V|-1 + |U|- 1 -\mathrm{odd}(G-U)) + 1 = \dfrac{1}{2}(|V|+|U| - \mathrm{odd}(G - U)). </tex>#:# Для каждой вершины <tex>v</tex> есть максимальное паросочетание <tex>M</tex> которое не покрывает <tex>v</tex> (например <tex>C_3</tex>)

Пусть <tex>G </tex> {{---}} граф, <tex>U_1,{...},\ldots U_n</tex> {{---}} компоненты связности графа <tex>G(D(G))</tex>, <tex>D_i = G(U_i), C = G(C(G))</tex>. тогдаТогда:

# Графы <tex>D_1,{...},\ldots D_n</tex> {{---}} фактор-критические. <br># Любое максимальное паросочетание <tex>M</tex> графа <tex> G </tex> состоит из совершенного паросочетания графа <tex> C </tex>, почти совершенных паросочетаний графов <tex> D_1,{...},\ldots D_n </tex> и покрывает все вершины множества <tex> A(G) </tex> рёбрами с концами в различных компонентах связности <tex> U_1,{...},\ldots U_n. </tex> <br>

# Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1,{...},\ldots U_n</tex> {{---}} компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>U_i</tex> {{---}} компонента связности графа <tex>G - A</tex>, паросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (D_i) = \alpha (D_i - u) </tex> и по теореме Галлаи (выше) мы получаем, что граф <tex>D_i</tex> {{---}} фактор-критический.

# Пусть <tex>M</tex> {{---}} максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \ge geqslant |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>D_1,{...},\ldots D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1,{...},\ldots U_n</tex>.