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

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

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