Изменения

|statement= В [[Основные определения теории графов#defBiparateGraph | [двудольном]] <tex>k</tex>-[[Основные определения теории графов#defRegularGraph | регулярном]] с одинаковыми по размеру долями графе существует совершенное паросочетание.

# Возьмём <tex>L</tex> {{---}} произвольное подмножество левой доли. Рассмотрим подграф образованный <tex>L</tex> и множеством всех их соседей из правой доли <tex>R</tex>. Все вершины левой доли нашего подграфа будут иметь степень <tex>k</tex>, а степени вершин правой доли '''не превосходит''' <tex>k</tex>.# Посчитаем количество рёбер <tex>m_{L}</tex> в данном подграфе. В силу его двудольности это число будет равняться сумме степеней вершин одной из долей. <tex>m_{L} = \underset{{v\in L}}{\sum} deg(v) = |L|\cdot k = \underset{{u\in R}}{\sum} deg(u) \leqslant |R|\cdot k</tex>. Из этого мы получаем, что <tex>|L|\leqslant |R|</tex>.# Значит в данном графе выполняется [[Теорема Холла | Теорема Холла]]. Из чего следует, что в нём есть совершенное паросочетание.

В доказательство рассмотрим следующий алгоритм поиска такой раскраски: 1) Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством [[Основные определения теории графов#isolated_vertex | изолированных вершин]]