Ein Artikulationspunkt in einem zusammenhängenden Graphen G ist ein Knoten -

Question

Aufgabe :

Ein Artikulationspunkt in einem zusammenhängenden Graphen G ist ein Knoten, dessen Entfernung den
Zusammenhang von G zerstört, das heißt G ohne v ist nicht zusammenhängend.
Finden Sie einen 3-regulären, einfachen Graphen mit minimaler Anzahl von Knoten, der einen Artikulationspunkt besitzt. Zeigen Sie, dass es keinen kleineren Graphen geben kann, der die Eigenschaften erfüllt.

Problem/Ansatz:

ich bin da stecken geblieben , kann jemand dabei mir helfen ?

Danke .

Answer 1

~draw~ strecke(-7|2 -3|2){000};strecke(-7|-2 -3|-2){000};strecke(-7|2 -3|-2){000};strecke(-7|-2 -3|2){000};strecke(-7|-2 -7|2){000};strecke(-3|2 -1|0){000};strecke(-3|-2 -1|0){000};strecke(7|2 3|2){000};strecke(7|-2 3|-2){000};strecke(7|2 3|-2){000};strecke(7|-2 3|2){000};strecke(7|-2 7|2){000};strecke(3|2 1|0){000};strecke(3|-2 1|0){000};strecke(-1|0 1|0){000};zoom(7);aus ~draw~

Zum Beweis: Sei G ein zusammenhängender kubischer Graph, der einen Artikulationspunkt besitzt. Angenommen der Graph hätte weniger als 10 Knoten also \( \#G \le 8 \). Wenn wir in diesem Graph jetzt den Artikulationspunkt herausnehmen, erhalten wir einen Graphen \( H \) mit \( \#H \le 7 \) und \( n\ge 2 \) Zusammenhangskomponenten \( H_1,...,H_n \). Es gilt \( \#H_1 + \dotsm + \#H_n = 7 \).

Wäre \( \#H_i = 1 \) so hätte der Knoten von \( H_i \) in \( G \) maximal Grad 1. Widerspruch.

Wäre \( \#H_i = 2 \) so hätten die beiden Knoten von \( H_i \) in \(G\) maximal Grad 2. Widerspruch.

Damit also \( \forall i: \# H_i \ge 3 \) Es bleibt somit o.E. nur noch der Fall \( \#H_1 = 3 \) und \( \# H_2 = 4 \).

Die Knoten von \( H_1 \) haben maximal Grad 2. In \( G \) haben sie aber Grad 3, d.h. der entfernte Knoten hat eine Kante zu all den drei Knoten in \(H_1 \). Da sein Grad aber selbst 3 ist, kann er folglich keine Verbindung zu einem Knoten aus \( H_2 \) haben. Der Graph \( G \) ist also nicht zusammenhängend. Widerspruch.