Übung 2 (Uni Köln)

Lösungen zu der Übung vom 20.05. und 25.05.

Aufgabe 14

Lösung fehlt

Aufgabe 15

Lösung fehlt

Aufgabe 16

Lösung fehlt

Aufgabe 17

Lösung fehlt

Aufgabe 18

Aufgabe

Sei G = (V,E) ein zusammenängender und nicht-vollständiger Graph ohne Schlingen und Mehrfachkanten. Zeigen Sie, dass in G Knoten a, b und c existieren mit ${ab, bc} \subset E$ und $ac \notin E$ .

Lösung

Da G nicht vollständig, existieren Knoten a und x aus G, die nicht benachbart sind:

Da G zusammenhängend, existiert zwischen a und x ein kurzester verbundener Weg $P=a x_1 x_2 ... x_{n-1} x_n$ Da P ein kürzester Weg ist, existiert die Kante a x_2 nicht. Mit b = x_1 und c = x_2 haben wir die gesuchten Knoten gefunden.