Erreichbarkeit zwischen Städten/Aufgabe/2/Lösung

Es soll ${\displaystyle {}n\in \mathbb {N} }$ Städte geben. Davon betrachten wir zunächst die Stadt ${\displaystyle {}S_{1}}$, von der man aus die Städte ${\displaystyle {}S_{2},S_{3},...,S_{n-k}}$ (${\displaystyle {}k\in \mathbb {N} }$ und ${\displaystyle {}k\geq 2}$) erreichen kann. Angenommen man kann aber von all diesen Städten nicht zu den restlichen Städten ${\displaystyle {}S_{n-k+1},S_{n-k+2},...,S_{n}}$ gelangen, dann folgt die Umkehrung: die Städte ${\displaystyle {}S_{1},S_{2},...,S_{n-k}}$ sind von den Städten ${\displaystyle {}S_{n-k+1},S_{n-k+2},...,S_{n}}$ aus erreichbar. Somit verbleiben die Städte ${\displaystyle {}S_{n-k+1},S_{n-k+2},...,S_{n}}$ als mögliche Kandidaten, die die Behauptung erfüllen könnten.

Verfolgt man nun die gleiche Argumentation, wie im Falle von Stadt ${\displaystyle {}S_{1}}$, für die Stadt ${\displaystyle {}S_{n-k+1}}$ (von ${\displaystyle {}S_{n-k+1}}$ sind die Städte ${\displaystyle {}S_{n-k+2},S_{n-k+3},...,S_{n-k+m}}$ (mit ${\displaystyle {}m\in \mathbb {N} }$ und

${\displaystyle {}m\geq 2}$) erreichbar) verkleinert man die Anzahl der möglichen Kandidaten weiter: ${\displaystyle {}S_{n-k+m+1},S_{n-k+m+2},...,S_{n}}$. Dies kann man soweit führen, bis nur noch die beiden Städte ${\displaystyle {}S_{n-1}}$ und ${\displaystyle {}S_{n}}$ als mögliche Kandidaten übrig bleiben. Da man entweder von ${\displaystyle {}S_{n-1}}$ nach ${\displaystyle {}S_{n}}$ oder andersrum gelangen kann, erfüllt einer der beiden Städte auf jeden Fall die Behauptung.