Ungerichteter Graph/Blatt/Hinwegnahme/Zusammenhang/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

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.

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.