Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » zusammenhängender Graph?

zusammenhängender Graph?

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie. Pfad

hans25 aktiv_icon

10:19 Uhr, 26.05.2020

Sei

G = (V, E)

ein (ungerichteter) zusammenhängender Graph

Zeigen Sie, dass es immer einen Pfad der Länge

d

gibt wenn

d

der minimale Grad von

G

ist.

Ich komm irgendwie nicht drauf, wie ich das formal sauber schreiben kann.

ermanus aktiv_icon

10:55 Uhr, 26.05.2020

Hallo,

hier bietet sich vollständige Induktion über

d

an.
Induktionsanfang ist

d = 1

.

Gruß ermanus

michaL aktiv_icon

11:00 Uhr, 26.05.2020

Hallo,

beginne mit einer beliebigen Ecke

v_{1} \in V

(

G = (V, E)

).
Da

d_{G} (v_{1}) \geq n

gilt, gibt es (mindestens) ein

v_{2} \in V \ {v_{1}} = : V_{1}

mit

(v_{1}, v_{2}) \in E

.

Da

d_{G} (v_{2}) \geq n

gilt, gibt es (mindestens) ein

v_{3} \in V \ {v_{1}, v_{2}} = : V_{2}

mit

(v_{2}, v_{3}) \in E

.

Vielleicht kannst du ja irgendwie weitermachen?!

Mfg Michael

ermanus aktiv_icon

13:03 Uhr, 26.05.2020

Hallo,

hat denn schon jemand herausbekommen, wozu die Voraussetzung
"zusammenhängend" gut sein soll?
Oder lautet die Originalaufgabe vielleicht etwas anders als hier
dargestellt?

Gruß ermanus

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1504144

1504116

	Status: nicht eingeloggt	Noch nicht registriert?