Теорема Холла
Для подмножества пусть — множество всех правых вершин, смежных хотя бы с одной вершиной из . Каждая правая вершина считается один раз, даже если у неё несколько соседей в .
Теорема Холла утверждает, что паросочетание, насыщающее , существует тогда и только тогда, когда
Здесь насыщение означает, что каждая левая вершина насыщена. Условие говорит, что у каждого подмножества левых вершин различных соседей должно быть не меньше, чем вершин в нём.
Пусть каждая левая вершина насыщена. У вершин любого подмножества есть различных пар, и все они принадлежат . Следовательно,
Возьмём наибольшее паросочетание. Пусть оно оставляет левых вершин свободными.
Запустим поиск сразу из всех этих вершин. Переходим по рёбрам вне паросочетания из в и по рёбрам паросочетания из в , как при построении вершинного покрытия. Пусть и — посещённые вершины.
Каждый сосед принадлежит :
Обратно, в каждую вершину из поиск пришёл из соседа в . Отсюда
Каждая вершина из насыщена: если бы мы дошли до свободной правой вершины, получился бы увеличивающий путь. Эти правые вершины сопоставлены ровно насыщенным вершинам из .
Остальные вершины — это свободных стартовых вершин. Таким образом,
Это противоречит условию Холла для . Следовательно, если условие выполнено, наибольшее паросочетание насыщает .
Найдём наибольшее паросочетание. Если его размер равен , каждую левую вершину можно сопоставить. Иначе запускаем описанный выше чередующийся поиск. Он находит
Это подмножество объясняет, почему полное распределение невозможно: у его вершин слишком мало различных возможных пар.
Для множеств система различных представителей выбирает
причём все выбранные значения различны.
Создадим левую вершину для каждого множества и правую вершину для каждого различного значения. Соединим множество с каждым содержащимся в нём значением. Требуемый выбор — это ровно паросочетание, насыщающее левую долю.
Теорема Холла даёт условие
Каждая группа множеств должна содержать не меньше различных значений, чем множеств в группе. Считаем объединение их вариантов: при сложении размеров отдельных множеств общие значения были бы посчитаны несколько раз.