Beweis zur Graphentheorie gesucht

[Senior Sanchez]

Hoi,

Ich besuche momentan die Veranstaltung "Grundlagen der theoretischen Informatik" und bei einer Aufgabe bin ich total ins Grübeln gekommen.

Es geht um folgende Aufgabe...
"Beweisen Sie: Jeder ungerichtete Graph mit mehr als einem Knoten besitzt zwei Knoten vom gleichen Grad."

Meine Idee war dafür eine Art strukturelle Induktion zu nutzen. Angenommen, wir haben n Knoten. Dann ist der kleinste Graph, den man damit aufbauen kann, quasi ne verkettete Liste dieser Elemente ohne das ganze zu einem Kreis zu schließen. Da so ein Graph n-1 Kanten hat, haben zwei Graphen (Anfang und Ende) jeweils den Grad 1 und (n-2) Knoten den Grad 2.
Die Bedingung ist also erfüllt.

Nun wollte ich eine Kante hinzufügen. Wird diese Kante zwischen zwei Knoten gleichen Grades eingefügt, so erhöht sich bei beiden der Grad um 1 und die Bedingung bleibt erfüllt.
Nur fehlt mir jetzt der Ansatz um zu zeigen, dass es bei einer neuen Kante zwischen zwei Knoten unterschiedlichen Grades auch noch erfüllt ist.
Gibt es sonst zwei Knoten gleichen Grades, die nicht an der neuen Kantenbildung beteiligt sind, bleibt die Bedingung ja erfüllt. Aber es kann auch sein, dass eben durch die neue Kante eine neue Gleichheit eines Grades zu einem anderen Knoten erreicht wird.

Ich komme da momentan einfach nicht weiter. Ich habe über die Aufgabe seit gestern nachgedacht und mir fehlt die zündene Idee.
Hat jemand von euch einen Rat?

Danke

[HajottV]

Jeder ungerichtete Graph mit mehr als einem Knoten besitzt zwei Knoten vom gleichen Grad.

Och komm, das ist doch echt einfach.

Sei n > 1 die Zahl der Knoten im ungerichteten Graphen G.

1. Fall: Es gibt einen Knoten k0 in G mit grad(k0) = 0

Damit gilt für alle Knoten k in G: grad(k) < n - 1 (jeder Knoten kann maximal mit jedem anderen Knoten verbunden sein, hat also maximal n - 1 Kanten, aber mit k0 ist keiner verbunden).

Für alle n Knoten in G gibt es also n - 1 mögliche Grade. Damit müssen zwei Knoten den gleichen Grad haben.

2. Fall: Es gibt keinen Knoten k0 in G mit grad(k0) = 0.

Für jeden Knoten k gilt damit: 1 <= grad(k) <= n - 1.

Damit haben wir wieder die Situation, daß wir n - 1 Grade auf n Knoten verteilen müssen, womit wieder zwei Knoten den gleichen Grad haben müssen.

Gruß

Jörg

[Senior Sanchez]

Argh, du hast Recht!
Das mir das nicht aufgefallen ist.

Vielen Dank :)

[Gast]

Blöde Frage zu ungerichteten Graphen:

Kann in einem ungerichteten Graph ein Knoten nicht auch mit sich
selbst verbunden sein? Dann gilt obige Aussage nicht.

[DocEW]

Stimmt. Und ebenso gilt die Aussage nicht für Multigraphen.

[Senior Sanchez]

Japs, da habt ihr schon Recht und in der Form war die Aufgabe schlampig gestellt.
Mir war aber schon klar, dass Multigraphen und Knoten mit einer Kante die ihn mit sich selbst verbindet, wurden ausgeschlossen.