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?