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)=(\genfrac{}{}{0ex}{}{n}{2})=\frac{n\ast (n-1)}{2}$

Lösungsvorschlag von neo

Aus der Angabe ablesbar (mithilfe von 305):
${\alpha }_0(G)>4$
$V(G^{\prime })=V(G)$
$E(G^{\prime })=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\wedge \mathrm{\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\ge 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\ast |E(G)|=2\ast 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\ast 4}{2}=10\to {\alpha }_1(G^{\prime })={\alpha }_1(K_5)-{\alpha }_1(G)=10-4=6$
Da $V(G)=V(G^{\prime })\to {\alpha }_0(G)={\alpha }_0(G^{\prime })=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.