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

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

Если же этот путь проходит через то его участок между и должен иметь чётную длину по нашему предположению. Но тогда и участок этого пути между и имеет чётную длину. То есть мы нашли нечётный цикл, в который входит вершина (получается добавлением к участку пути между и ребра ). Выберем кратчайший путь от вершин этого цикла до вершины Заметим, что такой путь по определению проходит ровно через одну вершину нашего цикла (начинается в ней). Причём этот путь не может начинаться в поскольку как минимум вершина из этого цикла ближе к чем Обозначим найденный путь через ( — вершина цикла). Но тогда из в мы сможем добраться рёбрам цикла двумя способами, причём эти два пути будут иметь разную четность. Тогда, соединив подходящий путь с путём получим требуемый путь.