Необходимость очевидна. Достаточность (индукция по |A|): база $|A|=1$ тривиальна. Шаг: если для всех $S$ ⊊ $A$ выполнено $|N(S)| \geq |S|+1$ (строгое неравенство), сопоставим произвольную $a \\in A$ с произвольным $b \\in N(a)$, удалим их и применим индукцию к оставшемуся графу (условие Холла сохранится). Если же существует «жёсткое» $S: |N(S)| = |S|$, применим индукцию к подграфу на $S \\cup N(S)$ (по предположению паросочетание есть), а для $A$\S условие Холла восстанавливается через исходное условие. В обоих случаях получаем совершенное паросочетание.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!