* <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
|proof=
много-много и с картинками. :(Достаточно доказать, что <tex>D(G-a) = D(G)</tex>. <br><tex>1) </tex> покажем, что <tex>D(G − - a) /\supset D(G)</tex> : <br>Пусть <tex>u \in D(G)</tex>. Тогда существует максимальное паросочетание <tex> Mu </tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G </tex> покрывает a, то α<tex> \alpha (G - a) = α\alpha (G) - 1 </tex> и более того, если <tex> ax \in Mu</tex>, то <tex>Mu \setminus {ax} </tex> - максимальное паросочетание графа <tex> G - a</tex>, не покрывающее <tex> u</tex>. Таким образом, <tex>D(G - a) \supset D(G)</tex>. <br><tex>2)</tex>покажем, что <tex> D(G − a) /\subset D(G)</tex>: <br>Предположим, что существует максимальное паросочетание <tex>M' </tex> графа <tex> G - a</tex>, не покрывающее вершину <tex>v not \in D(G)</tex>. Пусть <tex> w \in D(G) </tex>- смежная с <tex> a \in A(G) </tex> вершина, а <tex> Mw </tex>- максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> w</tex>. Так как <tex> v not \in D(G)</tex>, максимальное паросочетание <tex> Mw </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(Mw \bigcup M') </tex> - очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> - компонента связности графа <tex> H</tex>, содержащая <tex>v</tex>. Так как <tex> dH(v) = 1</tex>, то <tex> P = H(U) </tex> - путь с началом в вершине <tex>v</tex>. В пути <tex>P </tex> чередуются рёбра из <tex> Mw и M'</tex>, причём начинается путь ребром из <tex>Mw</tex> . Так как <tex> dH(a) = 1</tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> Mw</tex>). Рассмотрим несколько случаев: <br>
'''a.''' Путь <tex>P </tex> кончается ребром из <tex> M' </tex> (см. рисунок)<br>Рассмотрим паросочетание <tex>Mv = Mw \oplus E(P) </tex> (симметрическая разность<tex> Mw и E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).Очевидно, <tex>Mv </tex> - максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
'''b.''' Путь <tex>P </tex> кончается ребром из <tex> Mw</tex>, вершина a - конец пути <tex>P</tex>. (см.рисунок)<br>Рассмотрим паросочетание <tex>Mv∗ = (Mw \oplus E(P)) \bigcup \{aw\}</tex>. Тогда <tex> Mv∗ </tex> - максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие.
'''c.''' Путь <tex> P </tex> кончается ребром из <tex> Mw, a \in V(P) </tex> (см. рисунок)Рассмотрим паросочетание <tex> M'' = M \oplus E(P)</tex>. Тогда <tex> |M''| = |M'| + 1</tex>, причём Mээ <tex>M'' \subset E(G - a)</tex>. Противоречие с максимальностью паросочетания <tex>M'</tex>.
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
А значит, <tex>D(G - a) = D(G)</tex>.
}}
|about = Галлаи, Эдмондс
|statement=
пусть дан граф Для графа <tex> G = (V, E).<br/tex>выполняется:тогда:<brtex>1) <tex> U = A(G) </tex> - множество свидетелей Татта-Бержа <br>2) <tex>2) С(G) </tex> - объединение всех четных компонент <tex>G - A(G)</tex> <br>3) <tex>3) D(G) </tex> - объединение всех нечетных компонент <tex>G - A(G)</tex> <br><tex>4) </tex> каждая компонента в <tex> G - A(G)</tex> - фактор-критическая
|proof=
1) Последовательно удаляя вершины множества<tex> A = A(G)</tex>, по лемме о стабильности мы получим:
