89
правок
Изменения
→Структурная теорема Эдмондса-Галлаи
# <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
|proof=
[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']]
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
А значит, <tex>D(G - a) = D(G)</tex>.
Так как <tex>D(G - a) = D(G)</tex>, то все вершины, которые были соседями <tex>D(G)</tex>, таковыми и остались. Однако по условию <tex> a \in A(G)</tex>, значит <tex>A(G - a) = A(G) \setminus \{a\}</tex>.
Так же заметим, что <tex>C(G - a) = V(G - a) \setminus (D(G - a) \cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))</tex><tex> = V(G) \setminus (D(G) \cup A(G)) = C(G)</tex>
Наконец, так как <tex> a \in A(G)</tex>, то все максимальные паросочетания в <tex>G</tex> включали <tex>a</tex>. Следовательно <tex>\alpha (G - a) < \alpha (G)</tex>. Однако заметим, что взяв любое максимальное паросочетания в <tex>G</tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M'</tex> на 1 меньше исходного, при этом <tex>M' \in E(G - a)</tex>. В свою очередь это самое большое паросочетание, которое мы могли теоретически получить в <tex>G - a</tex>. Следовательно <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
}}
