A gráf Euler-útjának megkeresése

Bizonyítás

Kiválasztunk egy pontot, majd elindulunk a rajta átmenő körön. Ha egy olyan csúcsra értünk, amely része egy másik körnek is amit még nem jártunk be, akkor elindulunk rajta (így ha ezt a kört bejártuk, akkor visszatérünk ahhoz a csúcshoz, ahonnan elhagytuk az eredeti kört, és ezt folytatjuk). Mivel összefüggő a gráf, így az összes kört bejártuk, tehát megtaláltuk az Euler-kört a gráfban.

A fönti algoritmus bárhonnan kezdhető. Most kitörlöm a bizonyítás elején behúzott élt az eredetileg páratlan fokszámú csúcsok között, így megszakítottuk az Euler-kört egy helyen. Így ha az egyik páratlan fokszámú csúcsból kezdjük el a fönt megtalált "kört" bejárni, akkor a másik páratlan fokszámú csúcsba érkezünk meg. Így megrajzoltuk a gráf Euler-útját.

Kössük össze a két páratlan fokszámú csúcsot! Most minden fokszám páros, így elvégezhetjük "A gráf felosztása diszjunkt körökre" című bizonyítást.