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

Man zeige mit Hilfe eines graphentheoretischen Modells, daß es unmöglich ist, daß bei 5 Personen, die jeweils drei anderen eine Karte senden, alle genau von jenen Karten erhalten, denen sie auch eine geschickt haben.

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 lt. Panholzer

siehe Bsp. 202 (ist quasi Erklärung für 201)

Ganz wichtig: Buch, Satz 2.13 (Handschlaglemma):

$\sum d(v)=2\cdot |E|$

In einem schlichten, ungerichteten Graph ist die Summe aller Knotengrade gleich der doppelten Kantenmenge.

Nehmen wir an, jeder der 5 Knoten ist mit je 3 anderen Knoten genau durch eine, ungerichtete Kante verbunden. Der Knotengrad $d(v)$ ist für jeden Knoten 3, d.h.: $\sum d(v)=3+3+3+3+3=15$. Das widerspricht $\sum d(v)=2\cdot |E|$, denn 15 kann unmöglich $2\cdot |E|$ sein (2 mal irgendwas muss immer eine gerade Zahl ergeben).

Das war's.

Anmerkungen

Hallo Leute, 

ganz verstehe ich die Antwort/Begrünung in dem Link nicht, weil laut Angabe geht ja nur hervor, dass der Weggrad 3 
(von jedem Knoten gehen 3 Karten/Kanten weg ist. 

Rein theoretisch könnten ja die vier anderen Knoten Karten an einen Knoten schicken - dh dann hätte mal einen 
Knotengrad von vier (hat alle vier Knoten als Nachbar)

Hab mir das mit insg. 5 Knoten aufgezeichnet - es ist so, dass der letzte Knoten nur mehr zwei Karten erhält
 (wenn von jedem Knoten 3 Kanten ausgehen). Es dürfte eher von der Gesamtanzahl der Knoten abhängen, 
dh. bei 4 Knoten funktioniert es, bei 6 Knoten funktioniert es....

Links

• siehe Informatik-Forum WS04