Jedną z możliwości jest przejście całego cyklu Eulera w punktach 4 – 8 całego cyklu. Jeśli ono nastąpi, następuje koniec dowodu, ponieważ późniejszy powrót do pętli WHILE w kroku 12 nic nie zmienia. W przeciwnym wypadku wszystkie pozostałe w grafie wierzchołki są parzystego stopnia (ponieważ usunęliśmy z każdego parzystą liczbę krawędzi), chociaż mogą nie być połączone. Wynika stąd, że każda spójna składowa grafu G’ pozostałego po usunięciu pewnego cyklu w krokach 4 – 8 posiada cykl Eulera. Usunięta właśnie ścieżka cykliczna łączy te trasy w cykl Eulera dla wejściowego grafu. Gdyby tak nie było, wówczas suma pozostałych spójnych składowych i usuniętego w krokach 4 – 8 cyklu nie byłaby grafem spójnym, co przeczy założeniu.
W krokach 9 – 12 opisanego algorytmu, zdejmując ze stosu kolejne wierzchołki przemierza się (od końca, ale to nie zmienia dowodu) ścieżkę cykliczną, zbaczając z niej w każdym przypadku, gdy natrafi się na nieizolowany wierzchołek (gdy spełniony będzie warunek 4).