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

Назовем нечетные вершины А и Б. Выберем начальную нечетную вершину А и будем идти по ребрам (каждый раз по новым) до тех пор, пока не встретим вершину, в которой мы уже были (то есть замкнемся) или не придем в В (так как из всех остальных мы обязательно можем выйти, как только зашли в них).

Если мы пришли снова в выбранную начальную вершину А, то можем снова из нее выйти, так как ее степень нечетна (будем считать, что мы снова начали путь, выкинув прошедшие ребра). Продолжим путь.

Если мы снова попали не в начальную вершину (и не в Б), то мы снова можем из нее выйти, так как сейчас мы зашли в нее на один раз больше, чем вышли (а ее степень четна, то есть можем еще раз выйти по новому ребру). Продолжим путь.

Если же мы попали в Б и еще остались какие-то ребра, то хотя бы одно оставшееся ребро связано с нашим пройденным путем (так как граф связный). Тогда у вершины, которая соединена этим ребром с вершиной из нашего пути (назовем вершину из пути С), степень нечетна (если вершина не А и не Б) или четна (если это вершина А или Б), то есть из нее можно выйти. Идем далее по этим ребрам из С (по новым каждый раз и не из пути), как и раньше делали с путем. Тогда мы всегда можем идти дальше, пока не вернемся обратно в С. Теперь просто вставим этот участок в наш путь.

Таким образом мы сформируем путь по всем ребрам (так как их конечное число).