27
правок
Изменения
Нет описания правки
|proof=
<tex>\Rightarrow</tex> <br>
Очевидно, что если существует полное паросочетание, то для любого <tex>A \subset L </tex> выполнено <tex>|A| \leqslant |N(A)|</tex>. У любого подмножества вершин есть по крайней мере столько же ''соседей'' ("''соседи по парасочетанию"паросочетанию'').
<tex>\Leftarrow</tex> <br>
# В <tex>H_R</tex> входят только насыщенные вершины.
# <tex>N(H_L) = H_R</tex>
# В <tex>H_L</tex> по крайней мере <tex>H_R+1</tex> вершин ("''соседи" '' по паросочетанию для каждой вершины из <tex>H_R</tex> и ещё одна вершина, которую пытаемся добавить).
Цепь <tex>{4, 7, 3, 8}</tex> является удлиняющей для текущего паросочетания.
Увеличив текущее парасочетание вдоль этой цепи, мы насытим вершину с номером <tex>4</tex>.
==Примечания==
