Процессы и алгоритмы

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

Рассмотрим какого-нибудь участника Найдём участника с которым не знаком. Такой есть, поскольку при иначе задача решена. Добавим в компанию к Далее хочется найти участника с которым не знакомы и потом найти участника с которым не знакомы и и так дальше до тех пор, пока мы не получим компанию из попарно незнакомых участников.

Покажем, что на любом шаге мы сможем добавить в компанию очередного участника. Пусть мы уже выбрали участников Предположим, что не существует участника, с которым каждый не знаком. Получается, что каждый из оставшихся участников знаком хотя бы с одним из Это значит, что суммарно из всех вершин выходит хотя бы рёбер. С другой стороны мы знаем, что из них выходит не более рёбер. Получается, что что равносильно Заметим, что при последнее неравенство неверно, то есть в этом случае задача решена. А если то задача также решена.