Задача
COM-B2-M07-P016 Эйлеров цикл: достаточность
Докажите, что если конечный связный граф имеет только чётные степени, то в нём есть замкнутый обход, проходящий по каждому ребру ровно один раз.
Возьмите максимальный замкнутый обход и, если остались рёбра, вставьте ещё один цикл.
Начнём из любой вершины и идём по неиспользованным рёбрам, пока можем. Так как степени чётны, застрять в вершине, отличной от начальной, невозможно: каждый вход требует ещё один выход. Поэтому получим замкнутый обход.
Выберем замкнутый обход с максимальным числом рёбер. Если он использует не все рёбра, то из связности найдётся вершина обхода, из которой выходит неиспользованное ребро в ещё неиспользованную часть. Начиная с неё и двигаясь по неиспользованным рёбрам, снова получим замкнутый обход, который можно вставить в первый. Это увеличит число использованных рёбер, противоречие.
Значит, максимальный обход использует все рёбра.
Это уже полноценная олимпиадная лемма, не просто факт.