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

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