Zeigen Sie: Wenn G nicht zusammenhangend ist, so ist G(Strich) zuammenhängend.

Question

Aufgabe:

Es sei \( G=(V, E) \) ein einfacher Graph. Der Komplementgraph \( \bar{G}=(V, \bar{E}) \) von \( G \) besteht aus der gleichen Knotenmenge wie \( G \), wobei zwei Knoten genau dann verbunden sind, wenn sie im ursprünglichen Graphen \( G \) nicht verbunden waren:

\( \bar{E}=\left\{\left\{v, v^{\prime}\right\} \mid v, v^{\prime} \in V,\left\{v, v^{\prime}\right\} \notin E\right\} \)

Zeigen Sie: Wenn G nicht zusammenhängend ist, so ist \(\overline G\) zuammenhängend.

Answer 1

Seien v,w beliebige Ecken. Ist die Kante vw nicht in G, so ist sie im Komplement und wir haben einen Weg von v nach w im Komplement. Ist die Kante vw in G, so liegen v,w in der selben (Zusammenhangs)komponente von G. Da G nicht zusammenhängend ist, gibt es eine weitere Komponente, wir wählen eine ecke u daraus. Weder vu noch wu sind in G, d.h. vuw ist ein Weg von v nach w im Komplement. D.h. alle elemente kann man durch einen Weg (mit länge 1 oder 2) verbinden.

Comments

Hallo, hat man dies dann nicht nur für Graphen mit drei Knoten gezeigt? Ist der Beweis so vollständig?