89
правок
Изменения
Нет описания правки
{{Лемма
|id = lem2
|statement= В [[Основные определения теории графов#defBiparateGraph | [двудольном]] <tex>k</tex>-[[Основные определения теории графов#defRegularGraph | регулярном]] с одинаковыми по размеру долями графе существует совершенное паросочетание.
|proof=
# Возьмём <tex>L</tex> {{---}} произвольное подмножество левой доли. Рассмотрим подграф образованный <tex>L</tex> и множеством всех их соседей из правой доли <tex>R</tex>. Все вершины левой доли нашего подграфа будут иметь степень <tex>k</tex>, а степени вершин правой доли '''не превосходит''' <tex>k</tex>.
