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.