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

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