0
Hallo zusammen und frohes Neues, meine Übungsgruppe und ich verzweifeln momentan an diesen beiden Aufgaben. Hat jemand einen Tipp oder Ansatz?
4. Zeigen Sie: Jeder Graph G mit δ(G) ≥ 2 enthält einen Kreis der Länge mindestens
δ(G) + 1.
Hinweis: Wählen Sie zunächst einen Weg maximaler Länge. Argumentieren Sie, warum man aus einigen der Knoten dieses Weges einen Kreis der gesuchten Länge bilden kann.
5. Ein Baum ist ein zusammenhängender Graph, der keine Kreise enthält. Zeigen Sie, dass ein Graph G genau dann ein Baum ist, wenn zwischen je zwei verschiedenen Knoten von G genau ein Weg existiert
Vielen Dank
4. Zeigen Sie: Jeder Graph G mit δ(G) ≥ 2 enthält einen Kreis der Länge mindestens
δ(G) + 1.
Hinweis: Wählen Sie zunächst einen Weg maximaler Länge. Argumentieren Sie, warum man aus einigen der Knoten dieses Weges einen Kreis der gesuchten Länge bilden kann.
5. Ein Baum ist ein zusammenhängender Graph, der keine Kreise enthält. Zeigen Sie, dass ein Graph G genau dann ein Baum ist, wenn zwischen je zwei verschiedenen Knoten von G genau ein Weg existiert
Vielen Dank
Diese Frage melden
gefragt
jokerina96
Punkte: 15
Punkte: 15