Принцип крайнего

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

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

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