Zeigen sie : Für jeden zusammenhängenden Graphen G mit n 1 Knoten gibt es einen Knoten v, sodass G nach dem

Question

Aufgabe:

Zeigen sie : Für jeden zusammenhängenden Graphen G mit n > 1 Knoten gibt es einen Knoten v, sodass G nach dem
Löschen von v (samt inzidenter Kanten) zusammenhängend bleibt

Problem/Ansatz:

Ich habe versucht, zwei Szenarien zu erstellen, in denen der Graph ein Baum und kein Baum ist, aber ich bin nicht durchgekommen.

Answer 1

Hallo :-)

Den Fall zu betrachten, dass dein zusammenhängender Graph zunächst ein Baum ist, ist keine schlechte Idee. Denn dort gibt es mindestens ein Knoten \(v\), welches nur eine inzidente Kante hat. Das bedeutet: Beim Entfernen von \(v\) bleibt der restliche Graph immernoch zusammenhängend. (*)

Jetzt nimm dir irgendeinen zusammenhängenden Graphen \(G=(V(G),E(G))\) daher und betrachte davon einen beliebigen Knoten \(w \in V(G)\). Algorithmen wie Tiefen -oder Breitensuche liefern einen aufspannenden Baum \(B\) als Teilgraphen von \(G\), mit \(V(G)=V(B)\). Jetzt kannst du analog wie in (*) argumentieren.