20
правок
Изменения
м
Нет описания правки
<br>
<tex>A(G)\supset H</tex><br>
Предположим противное, : пусть существует вершина <tex>x\notin A(G)</tex>, принадлежащая всем максимальным барьерам. По [[ Декомпозиция Эдмондса-Галлаи#barier_struct3| теореме о структуре барьера]] <tex>x\in C(G)</tex>.<br>
Рассмотрим максимальное паросочетание <tex>M</tex> графа <tex>G</tex>, пусть <tex>xy\in M</tex>.<br>
Докажем, что <tex>B = A(G)\cup \{ y \}</tex> {{---}} барьер графа <tex>G</tex>. Так как <tex>|B| = |A(G)| + 1</tex>, достаточно доказать, что <tex>\mathrm{odd}(B)\ \geqslant \mathrm{odd}(A(G))\ + 1</tex>.<br>
