Гуляем по графу

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

1.

Между любыми двумя вершинами нет ребра при Если это не так, то мы сможем выбрать цикл меньшей длины на ребрах в котором участвует ребро

2.

Ни из какой вершины не ведет более одного ребра в вершины Предположим противное, тогда проведены ребра и Если тогда мы нашли треугольник, что противоречит условию, иначе мы можем выбрать новый цикл меньшей длины, в котором будут участвовать вершина

Удалим из все вершины, которые лежат в и все ребра, которые им инцидентны. Тем самым мы удалили ребро цикла, 0 ребер внутри цикла и не более ребер между вершинами и то есть суммарно не более ребер. Тем самым, в графе осталось не более вершин (потому что в цикле по условию хотя бы вершин) и хотя бы рёбер.

Повторим наш алогритм еще раза. После применения c номером мы имеем граф, в котором не более вершин и хотя бы ребер.

Наконец, перед последней итерацией, мы получим граф, в котором не более вершин и хотя бы ребер, в котором найдем последний цикл.