Изменения

|statement=Пусть <tex>B</tex> - минимальный по включению [[Декомпозиция Эдмондса-Галлаи#def1 | барьер]] <tex>G</tex>, тогда каждая вершина <tex>B</tex> - центр лапы в <tex>G</tex>.|proof=Пусть <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя компонентами связности графа <tex>G \setminus B</tex>.<br> Обозначим <tex>B' = B\setminus x</tex> <br>Найдём соотношение между <tex>\mathrm{odd}(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex> <br>Рассмотрим возможные случаи количества компонент связности в <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности(компоненты в <tex>B</tex> нас не интересуют)<br># <tex>x</tex> смежна с двумя компонентами связности <tex>G \setminus B</tex>.<br>#:a) Одна четная, другая - нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> <br>#:b) Обе чётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> <br>#:c) Обе нечётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> <br>#<tex>x</tex> смежна с одной компонентой связности <tex>G \setminus B</tex>.<br>#:a) Она чётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> <br>#:b) Она нечётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> <br># <tex>x</tex> не смежна ни с какой компонентой связности <tex>G \setminus B</tex> : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> <br>