133
правки
Изменения
Нет описания правки
То есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G)</tex><br>
Тогда возможны два случая:
#Если выполняется равенство <tex>\mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G)</tex>, то, по определению , <tex>B'</tex> является барьером. <br>#:Но <tex>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условиютеоремы. <br>
#Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то <br>
#:<tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\</tex>, что противоречит [[Декомпозиция Эдмондса-Галлаи#Th_Berge| теореме Бержа]]. <br>
== Источники информации ==
* Карпов Д. В. Д. - Теория графов, стр 55
