Graphentheorie: Zeigen sie, dass so ein Graph nicht existiert.

Question

Aufgabe:

Beweisen Sie: Es gibt keinen einfachen ungerichteten Graphen mit 5 Knoten und deg(v) = 3 für alle Knoten v.

Lösungsidee:

Angenommen, es gäbe so einen Graphen. Da G einfach ist, hat der Graph keine Schleifen und es gibt keine parallelen Kanten. D.h. an jeder Kante sind zwei paarweise verschiedene Knoten beteiligt. Da der Grad aller 5 Knoten 3 ist, bedeutet das, dass der Graph (3*5)/2 Kanten hätte. Dies kann aber nicht sein, da das keine natürliche Zahl ist. Ein Widerspruch, also gibt es keinen solchen Graphen.

Meine Frage ist, ob die Argumentation so in Ordnung ist. Bin mir nicht ganz sicher.

Comments

Ja, das ist richtig. Wenn Du diese Lösung aufschreiben, würde ich noch den Satz mit der Formel erwähnen, also evtl. Handschlag Lemma