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

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