Handschlaglemma - Beweis durch Induktion

Neue Frage »

Einskommanull Auf diesen Beitrag antworten »
Handschlaglemma - Beweis durch Induktion
Meine Frage:
Hi, ich soll das Handschlaglemma durch vollständige Induktion über m >= 1 beweisen.
Wobei m = |E|

Ich stehe da glaub ich gerade etwas auf dem Schlauch....




Meine Ideen:

deg(v) = 2*m

Induktionsanfang für |E| = m = 1:

2*1 = deg(1), weil Kanten nicht ins leere Verlaufen können, d.h. auf jeder Seite der Kante ist ein Knoten, jeder hat dann den anderen als Nachbar, d.h. jeder Knoten hat den Grad 1.
Und 1+1 = 2*1 = 2.

Zu zeigen ist nun, dass das sich die Summe der Grade um 2 erhöht, wenn ich die Kantenanzahl um 1 erhöhe.

Meine Idee nun für m -> m+1:

deg(v) = 2*(m+1) = 2m+2

da ich beim Induktionsanfang die Richtigkeit der Formel deg(v) = 2*m bewiesen habe, kann ich statt 2m+2 auch deg(v) +2 schreiben, womit das ganze Bewiesen wäre.


Mein Gefühl sagt mir aber, dass das nicht korrekt bewiesen ist.

Ein kleiner Denkanstoß wäre super.

Vielen Dank !

lg
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »