133
правки
Изменения
Нет описания правки
#: 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>. <br>#: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br>Рассмотрев случаи, видим, что для Для любого из них случаев выполнено: <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br>
<tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex>. <br>
Тогда <tex> \mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G) </tex>. <br>
