Для начала отметим, что теорема 7.1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.
Пусть G (X, E) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.
1°. Пусть a — произвольная вершина графа G. Возьмем любое ребро e 1=(a, x 1), инцидентное вершине a, и положим m = { e 1}.
2°. Рассмотрим подграф G 1(X, E\ m1). Возьмем в качестве e 2 ребро, инцидентное вершине x 1 и неинцидентное вершине a, которое также не является мостом в подграфе G 1 (если такое ребро e 2 существует!). Получим простую цепь m2 = { e 1, e 2}.
3°. Пусть e 2 = (x 1, x 2), x ¹ a. Рассмотрим подграф G 2(X, E\ m2) и удалим из него все изолированные вершины. В полученном подграфе выберем ребро e 3Î E\ m2, инцидентное вершине a, которое не является мостом в подграфе (если такое ребро e 3 существует!). Получим простую цепь
m3 = { e 1, e 2, e 3}.
Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл m = { e 1, e 2, …, en }, где n — число ребер графа G (X, E).