133
правки
Изменения
Нет описания правки
|about=следствие из теоремы
|statement=Пусть <tex>G</tex> {{---}} связанный граф, не содержащий лапы, <tex>v(G)</tex> чётно. Тогда <tex>G</tex> имеет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof=доказательство Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>. Тогда, по предыдущей теореме имеем <tex>B = \varnothing </tex>.<br>По условию <tex>G</tex> {{---}} связный граф с чётным числом вершин <tex>\Rightarrow </tex> <tex>\mathrm{odd}(необязательноG\setminus \varnothing )\ = 0 </tex> <br><tex>B</tex> {{---}} барьер <tex>\Leftrightarrow \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = \mathrm{def}(G) = 0 </tex>. Значит, количество вершин, не покрытых [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием]], равно 0, т.е. существует совершенное паросочетание.
}}
