Паросочетания и лемма Холла

В одну сторону лемма очевидна. Докажем, что если для любого набора из юношей количество знакомых им в совокупности девушек не меньше то каждого из них можно поженить на знакомых девушках. Создадим для каждого юноши его клон, не считая его самого. Нетрудно убедиться, что для полученного графа выполняется условие леммы Холла. Следовательно, в полученном графе есть паросочетание, покрывающее юношей. Тогда можно каждого юношу поженить на жёнах его клонов и получить требуемое.