Достаточность

Доказательство проводим по индукции по числу юношей.

1. , так как по условию каждый юноша знаком по крайней мере с одной девушкой, женим его на ней.

2. Пусть теорема верна для любого числа юношей меньше , при условии, что любые юношей знакомы не менее чем с девушками.

3. Докажем, что она верна для юношей.

Рассмотрим 2 случая:

а) Пусть любые юношей знакомы в совокупности не менее чем с девушкой (т.е. условие теоремы выполняется с запасом). Тогда берем – того юношу и женим его на любой знакомой девушке. Остались юноша, причем любые из них знакомы не менее, чем с девушками. По индуктивному предположению, их можно женить.

б) Существует группа из юношей, знакомых ровно с девушками . Причем по условию теоремы, любые из этих юношей знакомы не менее, чем с девушками, , по индуктивному предположению этих юношей можно женить на знакомых девушках.

Осталось юношей, это меньше, чем , но надо проверить, что любые из этих юношей знакомы не менее, чем с девушками из числа оставшихся (мы ведь часть девушек забрали, это могли быть знакомые оставшихся юношей). Только в этом случае мы сможем воспользоваться индуктивным предположением.

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

Следовательно, по индуктивному предположению, оставшихся юношей можно женить на знакомых им девушках из числа оставшихся.

Замечание. Если , это означает, что любая группа юношей числом меньше знакома не менее, чем с девушкой и только ровно юношей знакомы с девушками. Тогда берем любого юношу, женим на знакомой девушке. Остается юноша, из которых любые знакомы не менее, чем с девушками, т.е. приходим в ситуацию а).

Для графов теорему Холла можно сформулировать так: построить совершенное паросочетание в графе можно тогда и только тогда, когда любые вершин множества смежны в совокупности не менее, чем с вершинами множества .