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

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

Докажем оценку. Выберем наибольшее паросочетание Тогда так как среди любых вершин есть ребро, то в паросочетание не вошло не более вершин. А так как и в нашем графе, и в чётное число вершин, то в не вошло не более вершин. Добавим к по одному ребру из каждой вершины, не вошедшей в максимальное паросочетание. Пусть в не вошло вершин. Тогда получившееся множество рёбер имеет не более

Приведём пример, где меньше рёбер взять не получится. Разобьем людей на троек и группу из человек. Пусть люди в тройках обменяются письмами по циклу, а в группе из человек (один из которых Дед Мороз) все послали письмо Деду Морозу, а Дед Мороз любому из остальных девяти людей. Тогда в каждой тройке мы должны взять минимум два ребра, а в группе из человек мы должны взять хотя бы рёбер. Итого Осталось доказать, что пример подходит под условие. Это так, потому что среди любых человек найдется или человека из какой-то тройки, или вся группа из человек, внутри которой аж рёбер.