Graphentheorie: jede Person mit genau fünf anderen befreundet sein aus einer Gruppe von 21 Mitgliedern

Question

Aufgabe:

Wir betrachten eine Gruppe mit 21 Personen. Ist es möglich, dass in dieser Gruppe jede Person mit genau fünf anderen befreundet ist? Hier wird angenommen, dass die Relation befreundet sein symmetrisch ist, d.h. wenn A mit B befreundet ist, dann auch B mit A.

Problem/Ansatz:

Diese Aufgabe soll mit dem Thema der Graphentheorie gelöst werden. Ich Bitte um Hilfe :) 

Comments

Wenn die 21 Personen in einem Graphen durch die Knoten repräsentiert werden, wie könnte man dann die Eigenschaft "befreundet" im Graphen darstellen?

---

Durch die Kanten, die die Eckpunkte (hier die Personen) verbindet?

---

Genau. Wie kann man dann graphentheoretisch ausdrücken, dass jede Person genau 5 Freunde hat?

---

Bin mir nicht sicher. Einen zusammenhängenden Graphen "bauen" aus 6 Personen. Dadurch kommt es zu 5 Kanten. Und das so oft, bis es 21 Personen gibt. Dies ist aber unmöglich, da 6 kein Teiler von 21 ist. Also kann kann es nicht dazu kommen, dass jede Person genau 5 Freunde hat.

Beweisen dann mit 2k=∑d_E ?

Answer 1

Benutze den Tipp von mathhilf (s.o.) um den Grad der Knoten zu finden. Dann benutze den Satz, dass in einem Graphen \((V,E)\) mit \(m\) Kanten gilt: \(\sum\limits_{v\in V} deg (v) = 2m\).

Comments

\( \sum\limits_{v∈V}^{}{deg(v)} \) = n*d= 21*5 = 105

\( \sum\limits_{v∈V}^{}{deg(v)} \) = 2k

2k = 105 ⇒ m= 52,5 

52,5 kann aber nicht sein, da es sich um ganze Zahlen handelt. Also kann kein Graph existieren.

Oder?

---

Ja, aber kürzer: \(21\cdot 5\) ist ungerade, kann also nicht sein, fertig.

Zur Lösung gehört auch die saubere Beschreibung der Übertragung in graphentheoretische Begriffe. Zu rechnen ist ja so gut wie nichts.

Schlag auch den von mir zitierten Satz in Deinen Unterlagen nach, evtl habt Ihr andere Begriffe.

---

Okay. Super vielen Dank für die Hilfe :) !