Mathematik: Graphentheorie

Question

Aufgabe:

Beweisen Sie: Hat jeder Knoten in einem Graphen einen Grad von mindestens 2, dann enthält der Graph einen Kreis.

Problem/Ansatz:

Ich weiß bei dieser Aufgabe nicht wie ich anfangen soll. Mindestens heißt 1 oder 2 Kanten... Ich habe es mir auch erstmal graphisch vorgestellt, aber es hat im Endeffekt mir nicht geholfen wie ich anfangen soll. Hat jemand Tipps oder Ansätze für mich?

Answer 1

Wir nehmen an, dass Graph G endlich ist.
Sei \( \Omega \) die Menge aller Wege in G.
\( \Omega \) ist nicht leer und da G endlich ist gibt es einen Weg \( \omega \) maximaler Länge.
Sei v der von \( \omega \) zuletzt besuchte Knoten.
Nach Voraussetzung  besitzt v mindestens 2 Kanten \( e_1, e_2 \) und sei  \( e_1 \) die von \( \omega \)  zuletzt besuchte Kante.
Die zu \( e_2 \) inzidenten Knoten v,w liegen auf \( \omega \), sonst wäre der Weg 
\( \omega⤳e_2⤳ w \) länger als \( \omega \).

Dann ist v⤳ \(e_2 ⤳ [ \omega \text{ ab w} ]\) ein Kreis, da \( \omega \) in v endet.

Comments

Okay Danke dir, hört sich alles sehr plausibel an. Wäre aber glaube nicht von selber auf sowas gekommen.