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

Построим граф вершинами которого будут депутаты. Будем проводить между депутатами ребро, если они не враждуют друг с другом. Тогда в нашем графе степень каждой вершины не Теперь нам нужно найти в графе несамопересекающийся цикл, проходящий по всем вершинам.

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