Эйлеровы графы

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

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