TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 311

Sei $G$ ein schlichter Graph mit $\alpha _{0}(G)>4$. Man zeige, daß dann entweder $G$ oder $G^{k}$ (der komplementäre Graph, siehe Aufgabe 305) einen Kreis enthält.

Hilfreiches

Gibt es in einem ungerichteten Graphen $G$ zwei verschiedene Knoten $v,w$ 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: $\sum _{v\in V(G)}{d(v)}=2|E(G)|$
Kantenanzahl in einem vollständigen Graph $K_{n}$: $\alpha _{0}(K_{n})=n\to \alpha _{1}(K_{n})={\binom {n}{2}}={\frac {n*(n-1)}{2}}$

Lösungsvorschlag von neo

Aus der Angabe ablesbar (mithilfe von 305):
$\alpha _{0}(G)>4$
$V(G')=V(G)$
$E(G')=V\times V\setminus E(G)\cup \{(x,x)\mid x\in V\}$

Wenn $G$ einen Kreis enthält, so ist nichts zu beweisen. Wenn $G$ keinen Kreis enthält, so gibt es zwischen je zwei Knoten $u,v$ keine zwei verschiedenen Wege, welche $u$ mit $v$ 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: $d(x_{1})=d(x_{2})=1\land \forall x\in V(G)\setminus \{x_{1},x_{2}\}\mid d(x)=2$

Nun das Handschlaglemma verwenden für $\alpha _{0}(G)>4\to \alpha _{0}\geq 5$

$\sum _{v\in V(G)}{d(v)}=2|E(G)|\to \sum _{v\in V(G)\setminus \{x_{1},x_{2}\}}^{|V(G)|-2}{d(v)}+d(x_{1})+d(x_{2})=2+2+2+1+1=8=2*|E(G)|=2*4\to |E(G)|=4$

Nun wissen wir, dass der Graph $G$ 4 Kanten hat, wenn er keinen Kreis besitzt.
$\alpha _{1}(K_{5})={\frac {5*4}{2}}=10\to \alpha _{1}(G')=\alpha _{1}(K_{5})-\alpha _{1}(G)=10-4=6$
Da $V(G)=V(G')\to \alpha _{0}(G)=\alpha _{0}(G')=5$

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 $\alpha _{0}(G)>4$ gilt.

Kritik an Lösungsvorschlag:

Der Lösungsvorschlag sieht unzureichend aus. Die Schlussfolgerung, dass jeder Knoten ohne Kreis einen Knotengrad von 2 haben muss bis auf 2 Endknoten ist meiner Meinung nach falsch, da ein schlichter ungerichteter Graph auch ein Wald sein kann, d.h aus mehreren zusammenhangslosen Bäumen bestehen kann. Damit könnte ich 5 verschiedene Bäume machen, die nur aus einem Knoten bestehen zum Beispiel. Davon abgesehen ist auch die Annahme, dass ein Baum mit mehr als 4 Knoten nur 2 Endknoten hat auch falsch, er kann auch 3 oder mehr haben. Diese Fälle werden in der Lösung nicht in Betracht gezogen.