Zum Inhalt springen

Ungerichteter Graph/Blatt/Hinwegnahme/Zusammenhang/Fakt/Beweis/Aufgabe/Lösung

Aus Wikiversity


Es sei zusammenhängend und . Dann gibt es in einen verbindenden Weg von nach . Wenn in diesem Weg vorkommt, so jedenfalls nicht als Anfangs- oder als Endpunkt, da dies explizit ausgeschlossen ist. Wenn in der Mitte vorkommt, so in der Form , wobei die einzige Kante an bezeichne. Doch in diesem Fall kann man diesen Wegabschnitt herausnehmen und erhält einen kürzeren Weg von nach . Deshalb gibt es auch einen verbindenen Weg, wo gar nicht vorkommt.

Es sei nun zusammenhängend und seien . Wenn ist, so kann man direkt einen verbindenden Weg aus nehmen. Wenn

ist, so ist mit einem weiteren Knotenpunkt verbunden, und einen Weg in von nach kann man durch die Kante zu einem Weg in von nach fortsetzverlämgern.