Der Startpunkt liegt hier immer in der linken unteren Ecke, denn alle Wege, die links unten starten, enden im rechten unteren Eck und sind somit bis auf Symmetrie die selben.
Es gibt somit im wesentlichen 44 verschiedene Möglichkeiten das Haus vom Nikolaus zu zeichnen.
In den anderen Ecken kann nicht gestartet werden, da von ihnen eine gerade Anzahl von Kanten ausgeht, d.h. der Weg müsste wieder an der Ausgangsecke enden, was aber nach Satz (1) nicht geht.
Satz 1: Genau dann, wenn von jeder Ecke eine gerade Anzahl von Kanten ausgeht, gibt es einen Rundweg ( Eulerkreis ): dh. der Weg startet und endet in einer Ecke wobei er alle Kanten genau einmal durchläuft.
Satz 2: Genau dann, wenn keiner, oder genau zwei Ecken eine ungerade Anzahl von Kanten ausgeht, gibt es einen ( Eulerweg ): dh. der Weg durchläuft alle Kanten genau einmal.
Vereinfacht gesagt besteht ein Graph aus Ecken, die durch Kanten verbunden sein können.
Ein (ungerichteter) Graph heißt zusammenhängend, wenn sich zwischen je zwei beliebigen Ecken ein Weg aus Kanten finden lässt.