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

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

Es sei nun ${}G\setminus \{b\}$ zusammenhängend und seien ${}u,v\in G$. Wenn ${}u,v\neq b$ ist, so kann man direkt einen verbindenden Weg aus ${}G\setminus \{b\}$ nehmen. Wenn ${}u=b$

ist, so ist ${}b$ mit einem weiteren Knotenpunkt ${}w$ verbunden, und einen Weg in ${}G\setminus \{b\}$ von ${}w$ nach ${}v$ kann man durch die Kante ${}\{b,w\}$ zu einem Weg in ${}G$ von ${}b$ nach ${}v$ fortsetzverlämgern.

Zur gelösten Aufgabe