+1 Punkt
99 Aufrufe

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?

von

1 Antwort

+2 Daumen
 
Beste Antwort

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.

von

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...