Länge des Kreises in einem Graphen

Neue Frage »

Nisi93 Auf diesen Beitrag antworten »
Länge des Kreises in einem Graphen
Meine Frage:
Man beweise für eine beliebige positive ganze Zahl k größer als 1: Ein Graph, dessen Knoten alle einen Grad größer oder gleich k haben, besitzt einen Kreis der Länge größer oder gleich k+1.

Meine Ideen:
Also intuitiv ist dies klar. Der Grad der Knoten kann höchstens V-1 betragen. Definieren wir k:=V-1, so gibt es also k+1 Knoten, die zusammen verbunden einen Kreis ergeben. Zusätzlich müssen auch alle Knoten untereinander verbunden sein. Ist diese Idee soweit richtig? Wie kann ich es dann am besten mathematisch einwandfrei aufschreiben und beweisen?
Neue Frage »
Antworten »



Verwandte Themen

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