Eulersche Linien, Eulersche Graphen

1. Eulersche Linie:

Ein Kantenzug, der jede Kante eines Graphen G enthält, heißt offene oder geschlossene EULERsche Linie von .

2. Eulerscher Graph:

Ein zusammenhängender Graph, der eine geschlossene EULERsche Linie enthält, ist ein EULERscher Graph.

Beispiel

Der Graph G₁ (linke ober Abbildung) hat keine EULERsche Linie. Der Graph G₂ (rechte obere Abbildung) besitzt eine EULERsche Linie, ist aber kein EULERscher Graph. Der Graph G₃ (linke untere Abbildung) hat eine geschlossene EULERsche Linie und ist kein EULERscher Graph. Der Graph G₄ (rechte untere Abbildung) ist ein EULERscher Graph.

3. Satz von Euler-Hierholzer:

Ein Graph ist genau dann ein EULERscher Graph, wenn er zusammenhängend ist und jeder Knoten positiven geraden Grad hat.