TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 306

From VoWi
Jump to navigation Jump to search

Sei ein schlichter Graph mit . Man zeige, daß dann entweder oder (der komplementäre Graph, siehe Aufgabe 305) einen Kreis enthält.

Hilfreiches[edit]

Gibt es in einem ungerichteten Graphen zwei verschiedene Knoten und zwei verschiedene Wege, die diese Knoten verbinden, dann gibt es einen Kreis positiver Länge, der nur Kanten aus diesen beiden Wegen enthält.

Handschlaglemma:
Kantenanzahl in einem vollständigen Graph :

Lösungsvorschlag von neo[edit]

Aus der Angabe ablesbar (mithilfe von 305):




Wenn einen Kreis enthält, so ist nichts zu beweisen. Wenn keinen Kreis enthält, so gibt es zwischen je zwei Knoten keine zwei verschiedenen Wege, welche mit verbinden. Daraus folgt, dass jeder Knoten eines Graphen ohne Kreis den Knotengrad 2 haben muss, bis auf 2 Knoten, welche jeweils den Knotengrad 1 haben. (Dabei kann man sich einen Weg vorstellen, welchen man durch alle Knoten eines Graphen zeichnet. Die zwei Knoten mit Grad 1 wären Anfangs- bzw. Endknoten)

Formal dargestellt:

Nun das Handschlaglemma verwenden für



Nun wissen wir, dass der Graph 4 Kanten hat, wenn er keinen Kreis besitzt.

Da

Nun hat man also 6 Kanten zur Verfügung um sie auf 5 Knoten aufzuteilen. Dies kann man mithilfe des Schubfachprinzips lösen. Die 6 Kanten lassen sich nicht auf die 5 Knoten (Schubfächer) aufteilen, ohne dass zumindest 2 Kanten auf einen Knoten kommen. Damit wurde bewiesen, dass entweder ein Graph oder sein komplementärer Graph einen Kreis enthält, wenn gilt.