Теорема Холла

Решение задачи о свадьбах существует тогда и только тогда, когда любые юношей из знакомы в совокупности не менее, чем с девушками .

Необходимость. Если какие-то юношей знакомы менее чем с девушками, то уже этих юношей невозможно женить на знакомых им девушках.