Изменения
Нет описания правки
Тогда существует путь из <tex>x</tex> в <tex>y</tex>, который будет удлиняющим для паросочетания <tex>P</tex>(т.к из <tex>R'</tex> в <tex>L'</tex> мы проходили по ребрам паросочетания <tex>P</tex>). Увеличив паросочетание P вдоль этого пути получаем искомое паросочетание. Следовательно предположение индукции верно.
}}
==Примечания==Иногда теорему называют теоремой о свадьбах.Также теорема обобщается на граф, имеющий произвольное множество долей.
==Ссылки==
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BB%D0%BB%D0%B0 Теорема Холла — Википедия]
