Erreichbarkeit zwischen Städten/Aufgabe/Lösung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Es soll Städte geben. Davon betrachten wir zunächst die Stadt , von der man aus die Städte ( und ) erreichen kann. Angenommen man kann aber von all diesen Städten nicht zu den restlichen Städten gelangen, dann folgt die Umkehrung: die Städte sind von den Städten aus erreichbar. Somit verbleiben die Städte als mögliche Kandidaten, die die Behauptung erfüllen könnten.

Verfolgt man nun die gleiche Argumentation, wie im Falle von Stadt , für die Stadt (von sind die Städte (mit und ) erreichbar) verkleinert man die Anzahl der möglichen Kandidaten weiter: . Dies kann man soweit führen, bis nur noch die zwei Städte und als mögliche Kandidaten übrig bleiben. Da man entweder von nach oder andersrum gelangen kann, erfüllt einer der beiden Städte auf jeden Fall die Behauptung.
Zur gelösten Aufgabe