Zusammenhang Komplementgraph Graph

Question

Aufgabe:

Seit G = (V,E) ein einfacher ungerichteter Graph und G ̅= (V,E¯) der Komplementgraph mit
E¯ := {(u,v) ∈ V x V | (u,v) ∉ E}.

Problem/Ansatz:

2.1 Zeigen Sie: Mindestens einer der Graphen G oder G¯ ist zusammenhängend.
2.2 Widerlegen Sie: Höchstens einer der Graphen G¯ oder G ist zusammenhängend.

Answer 1

2.1. Sei \(G\) nicht zusammenhängend mit Zusammenhangskomponenten \(V_1,\dots,V_n\).

Sei \(v_i\in V_i\) für jedes \(i\in\{1,\dots,n\}\). Dann existiert in \(\overline G\) der Weg \(v_1\rightarrow \dots\rightarrow v_n\) auf dem jedes der \(v_i\) liegt.

Sei \(w\in V_1\). Dann existiert in \(\overline G\) der Weg \(v_1\rightarrow v_2 \rightarrow w\).

Also ist \(\overline G\) zusammenhängend.

2.2 Finde ein Beispiel.