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

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