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

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

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

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