Fünfter Beweis: Maximaler Graph und Äquivalenzrelation¶

In diesem Beweis wird angenommen, dass G ein Graph mit n Knoten und ohne p - Clique ist, welcher die maximale Anzahl an Kanten hat. Um \(\mid E \mid \le (1- \frac{1}{p-1}) \frac{n^2}{2}\) zu zeigen bedient sich dieser Beweis zudem folgender Behauptung:

Behauptung: G enthält keine drei Knoten u,v,w mit \(\{ v, w \} \in E\), aber \(\{ u, v \} \notin E\) und \(\{ u, w \} \notin E\)

Diese Behauptung beweisen wir durch Widerspruch. Hierzu unterteilen wir das Problem in zwei Fälle:

Fall 1: \(d(u) < d(v) \vee d(u) < d(w)\)

Nehmen wir an, dass d(u) < d(v) gilt, denn u und v sind austauschbar. Entfernen wir nun u, verdopplen wir v und nennen den neuen Knoten v’, wobei alle Kanten ebenfalls kopiert werden, sodass v’ die selben Nachbarn wie v hat. Der hieraus entstehende Graph G’ hat ebenfalls keine p-Clique, da v’ lediglich doppelte, so zu sagen parallele Verbindungen hinzufügt, eine bestehende Clique also nicht erweitert wird. Hieraus ergibt sich für die Kantentzahl:

Da G ein maximaler Graph ist, ist dies ein Widerspruch.

Fall 2: \(d(u) \ge d(v) \wedge d(u) \ge d(w)\)

Hier kopieren wir u zwei mal, da es vom Grad her maximal ist, wobei wie im ersten Fall die Kanten mitkopiert werden und entfernen dann v und w. Der hieraus entstehende Graph kann wieder keine p-Clique haben, da er eine bestehende Clique durch die Veränderung nicht erweitern würde. Für die Anzahl der Kanten ergibt sich:

Hierbei ergeben sich die \(2d(u)\) durch das doppelte Kopieren von u, die \(- (d(v) + d(w) - 1)\) vom entfernen von v und w, sowie der Kante vw. Die Ungleichung gilt, da \(d(u) \ge d(v) \wedge d(u) \ge d(w)\) gilt. Da G’ nun mehr Kanten hat G ergibt sich wieder ein Widerspruch, womit die Behauptung bewiesen wäre.

Definieren wir \(u \sim v :\Longleftrightarrow \{ u,v \} \notin E(G)\), so ist dies dank der bewiesenen Behauptung eine Äquivalenzrelation:

Reflexiv:

1. Dies gilt, da die hier betrachteten Graphen keine Kanten mit gleichem Start und Zielknoten erlauben.

Transitiv:

1. Dies ist exakt die oben bewiesene Behauptung.

Symetrisch:

Diese Äquivalenzrelation muss ebenfalls für alle vollständigen (p - 1) - partiten Graphen gelten, da dort lediglich Knoten aus unterschiedlichen Partitionen miteinander verbunden sind. Ein dritter Knoten muss also aufgrund der Vollständigkeit entweder mit einem der beiden oder beiden anderen verbunden sein. Dementsprechend gilt die Äquivalenzrelation auch für Turán Graphen, wodurch sowohl der maximale Graph, als auch der Turán Graph in einer Äquivalenzklasse sind.

Dementsprechend können wir unseren maximalen Graphen als einen solchen behandeln und die Aussage ist bewiesen, da wir die Behauptung schon im zweiten Beweis für einen (p - 1) - Turán Graphen gezeigt haben.