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

Aus VoWi
Zur Navigation springen Zur Suche springen

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.