Aufgabe:
Aufgabe 1
Sei G = (V, E) ein zusammenhängender ungerichteter Graph. Betrachten Sie zwei Wege P und Q, die maxi-
male Länge haben. 1 Zeigen Sie, dass P und Q mindestens einen gemeinsamen Knoten besitzen.
Hinweis: Beweisen Sie durch Widerspruch. Nehmen Sie an, dass die zwei Wege keinen gemeinsamen Knoten
haben. Konstruieren Sie dann einen längeren Weg.
Aufgabe 2
(8 Punkte)
Sei G = (V, E) ein zusammenhängender ungerichteter Graph. Sei d der durchschnittliche Knotengrad von G,
d.h. d = 2|E|/|V |. Zeigen Sie für alle c > 1, dass höchstens 1/c · |V | Knoten einen Grad größer als c · d haben
können.
Hinweis: Beweisen Sie durch Widerspruch. Nehmen Sie an, dass mehr als 1/c · |V | P
Knoten einen Grad größer
als c · d haben. Zeigen Sie einen Widerspruch zu dem Satz aus der Vorlesung, dass v∈V d(v) = 2|E|.
Aufgabe 3
Sei G = (V, E) ein Graph mit mindestens 2 Knoten. Eine Kante (u, v) heißt Schlinge, wenn u = v ist. Nehmen
wir an, dass G keine Schlingen enthält. Der Graph enthält ebenfalls keine Mehrfachkanten.
Zeigen Sie, dass es mindestens zwei Knoten in G gibt, welche den gleichen Grad besitzen.
Problem/Ansatz:
habe hier 3 Beispiele zur Graphentheorie, mit denen ich nicht fertig werde. Zu Aufgabe 1 und 2 hätte ich keinen Ansatz- Zu Beispiel 3 könnte ich, dass mittels einen Graphen zeigen, glaube aber nicht, dass dieses genug ist.
Würde mich über jede Hilfe freuen!
