Алгоритм направления ребер G - такой, что для всех вершин v выполняется in-deg(v) = out-deg(v)

Question

Пусть G = (V,E) - связный неориентированный граф, в котором все вершины имеют четные степени. Предложите алгоритм с линейным временем для направления ребер графа G так, чтобы в полученном ориентированном графе для всех вершин v выполнялось равенство in-deg(v) = out-deg(v)

Моя попытка:

1. Выберите произвольное ребро и найдите цикл Эйлера, обозначенный C=c1,c2, ..., cn
2. Пройдите через C и соедините каждый (ci,ci+1) для каждого i =1, ..., n.
3. Верните новый график.

Я думаю, что это правильно, но мне трудно доказать его правильность.

Буду признателен за вашу помощь!

Алгоритм направления ребер G - такой, что для всех вершин v выполняется in-deg(v) = out-deg(v)