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

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