Die Städte S1....Sn seien untereinander durch Straßen verbunden und zwischen zwei Städten gibt es

Question

Die Städte \( S_{1}, \ldots, S_{n}(n \geq 1) \) seien untereinander durch Straßen verbunden und zwischen zwei Städten gibt es immer genau eine Straße. Wegen Bauarbeiten sind zur Zeit alle Straßen nur in eine Richtung befahrbar. Zeigen Sie, dass es trotzdem mindestens eine Stadt gibt, von der aus alle anderen Städte erreichbar sind.
Hinweis: Vollständige Induktion.

Answer 1

O.b.d.A. seien von S_n aus alle Städte erreichbar.

Es wird die Stadt S_n+1 gebaut und mit allen anderen Städten verbunden.

Die Verbindung zwischen S_n und S_n+1 läuft entweder in die Richtung von S_n nach S_n+1, oder in die Richtung von S_n+1 nach S_n. Im ersten Fall sind alle Städte von S_n aus erreichbar. Im zweiten Fall sind alle Städte von S_n+1 aus erreichbar.