Ein ungerichteter Graph G ist genau dann ein eulerscher Graph, wenn G zusammenhängend ist (wenn also je zwei seiner Knoten durch eine Kantenfolge des Graphen verbunden werden können) und jeder Knoten geraden Grad hat (wenn also die Anzahl der an den Knoten angeschlossenen Kanten gerade ist, wobei eine Schleife doppelt gezählt wird, weil sie zweimal an den betroffenen Knoten angeschlossen ist).
Der vorliegende Graph ist zusammenhängend, enthält jedoch zwei Knoten mit ungeradem Grad (Knoten 1 und 2) und ist daher nicht eulersch.
Ein Eulerweg ist eine Folge von Kanten eines Graphen G, der jede Kante von G genau einmal enthält.
Ein Eulerkreis ist ein Eulerweg, dessen Anfangknoten gleich seinem Endknoten ist.
Es gilt:
Ein ungerichteter, zusammenhängender Graph G enthält genau dann einen Eulerweg, wenn G keinen oder genau zwei Knoten mit ungeradem Grad enthält. Enthält G keinen Knoten mit ungeradem Grad, dann ist der Eulerweg sogar ein Eulerkreis.
Der vorliegende Graph enthält genau zwei Knoten mit ungeradem Grad. Er enthält also einen Eulerweg, der aber kein Eulerkreis ist.
