Definíció: Euler-vonal egy G gráfban egy olyan vonal, amely az összes élt és össze csúcsot meglátogatja.
Az Euler-vonal (és záródó Euler-vonal) fogalma Leonhard Euler-ról kapta nevét. Euler egy akkor népszerű problémát vizsgált Königsberg városának hét hídjáról . A kérdés az volt, hogy lehet-e olyan sétát tervezni, amely az összes hídon pontosan egyszer halad át. A válasz nemleges és ennek meggondolása vezette el Eulert a következő tétel igazolásához.
Tétel (Euler-tétel): Egy gráfban akkor és csak akkor van záródó Euler-vonal, ha összefüggő és minden csúcs páros fokszámú.
Bizonyítás: A bizonyítandó egyik irány nyilvánvaló, hiszen záródó Euler-vonal létezése esetén gráfunk összefüggő (a vonal az összes csúcsot meglátogatja) a körvonal kiinduló=végpontján kívüli csúcsok esetén mindig áthaladunk (be, majd ki haladunk), ami párbállítja a csúcsra illeszkedő éleket. A kiinduló=végpontra az első kilépés és az utolsó belépésen túl mindig áthaladás történik, így itt is adódik a páros fokszám.
Lemma:
(i) Ha az x csúcs fokszáma páratlan, akkor a vonalnövelési
eljárás egy másik
(x-tól különböző) páratlan fokú csúcsban
fog elakadni.
(ii) Ha az x csúcs fokszáma páros, akkor a vonalnövelési
eljárás x-ben vagy egy páratlan fokú csúcsban
fog elakadni.
Ezekután, ha a vonalnövelési eljárás nem adja meg az egész gráfot, akkor egy olyan élből indítunk egy eddig be nem járt éleken haladó vonalnövelési eljárást, amelyet eddig még nem jártunk be, de kiindulópontját eddigi vonalunk már érintette. Az így kapott vonal (lásd lemma) zárt lész és eddigi vonalunkba beilleszthető. Ezen bővítési lépésekkel elérhetjük, hogy egy Euler-vonalhoz jussunk.
Megjegyzés: A bizonyításból az is adódik, hogy egy gráfban akkor és csak akkor van Euler-vonal, ha 0 vagy 2 csúcsnak fokszáma páratlan.