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.
