Wie lautet die Relation zwischen den Personen, die im Komplementgraph GC modelliert ist?

Question

Aufgabe:

In der Analyse von sozialen Netzwerken werden häufig Graphen untersucht, bei denen die
Knoten die Personen des Netzwerkes und die Kanten entsprechende Relationen zwischen den
Personen darstellen. Wir betrachten folgende Aussage: In jeder Gruppe von sechs Personen
gibt es eine Gruppe von drei Personen, die sich jeweils untereinander kennen, oder es gibt eine
Gruppe von drei Personen, die sich jeweils nicht kennen.

Problem/Ansatz:

1)  Beweisen Sie die Aussage für den Spezialfall, dass der maximale Grad
d max ∶= max {d(v) ∣ v ∈ V } ≥ 3.

2) Führen Sie den Fall max < 3 auf den Fall max ≥ 3 zurück, indem Sie den Komplementgraph
G^C = (V, (V × V) \ E) betrachten.
Wie lautet die Relation zwischen den Personen, die im Komplementgraph G^C modelliert ist?

Answer 1

Sei G=(V,E) der Graph, der die Beziehung "sind miteinander bekannt" modelliert.

1. Wenn es einen Knoten $x \in V$ mit $d(x) \geq 3$ gibt, seien die Nachbarn $x_1, \ldots x_k$, $k \geq 3$

1.1 Zwei der Nachbarn sind ebenfalls benachbart, sagen wir $x_1,x_2$. Dann ist $(x,x_1,x_2)$ ein Dreieck.

1.2 Wenn nicht, sind alle $x_1, \ldots, x_k$ nicht benachbart, das sind mindestens 3.

2. Wenn alle Knoten den Höchstgrad 2 haben, folgt aus dem handshake-lemma für die Zahl der Kanten:

$$2|E|=\sum_{v \in V}d(v)\leq 6 \cdot 2 \Rightarrow |E| \leq 6$$

Ein vollständiger Graph auf 6 Knoten hat 15 Kanten. Der komplementäre Graph $G^C$ hat also mindesten 9 Kanten. Ebenfalls wegen des Handshake-Lemmas. Muss darin ein Knoten einen Grad größer gleich 3 haben.....

Der komplmentäre Graph modelliert die Beziehung "kennen sich nicht".