TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 306

Man zeige dass es in jedem Graphen G mit n >= 2 Knoten wenigstens 2 Knoten mit gleichem Knotengrad gibt.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösung

• Lösung durch einen indirekten Beweis. Wir führen die Annahme dass es einen Graph G gibt, der keine 2 Knoten gleichen Grades hat, zu einem Widerspruch.
• Es sei also G ein Graph, der keine 2 Knoten gleichen Grades hat. Daraus folgt also, dass der Grad jedes Knotens verschieden sein muss.
• Es sei weiters n die Anzahl der Knoten in G. Man kann sich überlegen dass der Grad für jeden Knoten in G zwischen 0 (d.h. der Knoten ist mit keinem anderen Knoten verbunden) und n-1 liegen muss (d.h. der Knoten ist mit allen anderen Knoten verbunden).
• Da nun also genau die Knotengrade von 0 bis n-1 in Frage kommen und gleichzeitig jeder Knoten einen verschiedenen Grad haben muss (lt. obiger Forderung), heißt das also dass jeder Knotengrad von 0 bis n-1 genau einmal in G vorkommen muss, ansonsten würde sich das natürlich nicht ausgehen (kann man in diesem Sinn auch als bijektive Funktion interpretieren).
• Es folgt dass es in G einen Knoten gibt der den Grad n-1 hat.
• Der Knoten mit dem Grad n-1 verbindet alle anderen Knoten. Daraus folgt dass es keinen Knoten mit dem Grad 0 geben kann.
• Wir fordern aber dass jeder Knotengrad genau einmal vorkommt, auch ein Knoten mit dem Grad 0. Das führt somit zu einem Widerspruch.
• Es kann daher keinen Graphen geben, der lauter unterschiedliche Knotengrade hat. Daraus folgt, dass jeder Graph G zumindest 2 Knoten gleichen Grades besitzen muss, was zu zeigen war.

Der formale Nachweis kann ähnlich der "mündlichen" Argumentation analog geführt werden.

--Emkey08 00:55, 7. Dez 2007 (CET)

Diskussion

So erklärt von Tutor (GITTENBERGER) in Gruppe R

analog: Pidgeon-Hole-Prinzip

• Einfacher Graph
• 0 <= d(x) <= n-1
• Menge möglicher Knotengrade: M={0,1,...,n-1}
• M widerspricht sich selbst, weil einerseits ein Knoten mit 0 Verbindungen existiert, andererseits einer mit n-1 Verbindungen (dh 1 Verbindung zu jedem anderen Knoten)
• -> M muss entweder sein {0,...,n-2} oder {1,...,n-1}
• |M| < n -> mindestens zwei Knoten müssen den gleichen Knotengrad haben

braucht man lt. Tutor nur erklären (argumentieren), nicht "streng formal" anschreiben

Links

Diskussion Informatik-Forum WS05 Beispiel 549 alte Nummer, neu 203