Angenommen, es g¨abe schlechte Ecken, dann sei v die erste schlechte Ecke auf der Tour W . Wir haben dann d⁺_W (v) = d^-_W (v) < d(v), also wurde nach Regel 2 die markierte Kante (u, v) in der Richtung v   u noch nicht besucht. Es gibt also noch Kanten, die nicht durchlaufen wurden. Das bedeutet aber d⁺(u) =  d^-(u)  < d(u), d.h. der Vorg¨anger  u  ist auch schlecht, denn hier ist die zu u  inzidente Kante  v     u  noch nicht besucht worden. Dies steht aber im Widerspruch zur Wahl von v als erste schlechte Ecke. Also ist jede Ecke auf W  gut. Nach der Definition von gut ist jeder Nachbar einer guten Ecke ebenfalls gut, und die guten Ecken bilden einen zusammenh¨angenden Grapen. Da G zusammenh¨angend ist, muß also jede Ecke gut sein! Damit ist bewiesen, daß wir das Labyrinth mit dem o.g. Algorithmus durchlaufen k¨onnen, ohne uns irgendwo“festzufahrent’t’. Wie man jedoch am Beispiel sehen kann, gibt es verschiedene Touren unterschiedlicher L¨ange. Eine Abwandlung des Problems fragt nach der M¨oglichkeit, einen Weg zu finden, der jede Kante nur einmal enth¨alt (“Haus vom Nikolaust’t’). Einen sol- chen Graphen nennt man Eulerzug. Damit ein solcher Weg existiert, m¨ussen jedoch alle Ecken einen geraden Grad haben. Literatur [1] M. Aigner, Diskrete Mathematik, 4. Auflage, vieweg Verlag, 2001. 10