TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 304

Aus VoWi
Wechseln zu: Navigation, Suche

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

-- Etwas anders erkärt: Die möglichen Knotengrade sind 0, ..., n-1 bei n Knoten (ein Knoten kann maximal mit seinen n-1 Nachbarn verbunden sein im schlichten Graphen). n-1 und 0 schließen sich Gegenseitig aus: Ist ein Knoten mit n-1 (allen) verbunden, so ist keiner mit 0 verbunden. Es gibt also für n Knoten nur n-1 Knotengrade (0, ..., n-2 oder 1, ..., n-1) und laut Taubenschlaglemma haben dann 2 Knoten denselben Knotengrad.