Prof. Dr. R. Laue                                                                            WS0203
                                Graphentheoretische Optimierung
                                Übungsblatt 12
Abgabe: bis Donnerstag 30.1.03 12.00 Raum 736 Mathe NW2

URL:         /axel/graph_ws0203_blatt12.html
 


Aufgabe 25 k-fach zusammenhängend  (2+4+2+2 Punkte)

a) G sei ein  planarer Graph mit n Punkten. Sei nd die Anzahl der Punkte vom Grad höchstens d. Man zeige

nd >= (n(d-5)+12) / (d+1)

Hinweis (Abschätzung aus der Vorlesung beim Thema planare Graphen)

b) Man zeige, dass ein planarer Graph höchstens 5-fach zusammenhängend ist.

c) Gebe ein Beispiel für 4-fach zusammenhängend mit 6 Punkten

d) Zeigen Sie dass 5-fachzusammenhängende planare Graphen mindestens 12 Punkte haben.

e) Gebe ein Beispiel für 5-fach zusammenhängend mit 12 Punkten. (3 Extrapunkte)