TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 198

Man zeige mit Hilfe eines geeigneten graphentheoretischen Modells, daß es in jeder Stadt mindestens zwei Bewohner mit der gleichen Anzahl von Nachbarn gibt.

Lösungsvorschlag:

Lösungsmodell wäre ein Binärbaum, da in der Minimalkonfiguration (Wurzel und 2 Blätter) bereits die Bedingung erfüllt ist, ebenso gilt das für jeden Randknoten oder 2 beliebige Knoten in der Mitte des Baums. Leider eine falsche Überlegung auf Grund der nicht sehr präzisen Angaben.

Lt. Urbanek soll man zeigen, daß jeder Graph mindestens 2 Knoten (Nachbarn) vom selben Knotengrad besitzt.

Es existiert ein a,b enthalten in der Knotenmenge V(G) wobei a ungleich b ist.

0 $\leq$ d(a) < n und 0 $\leq$ d(b) < n

wobei n die Knotenanzahl und der Grad n-1 ist. Da 0 kein Nachbar von n-1 ist, müssen mindestens 2 Knotengrade gleich sein.

Hapi