Logik-Rätsel mit Graphen und Kombinationsmöglichkeiten

Question

Angenommen wir bauen ein Netzwerk aus Computer auf.
Aus Sicherheitsgründen darf es in diesem Netzwerk nicht vorkommen, dass es keine 3 Computer gibt, die sich alle direkt kennen (verbunden sind). Jedoch gilt für ein gutes Netzwerk, desto mehr Verbindungen, umso ein stabileres Netz. 
Beweise nun, dass in diesem Fall, bei einer Anzahl von 2*n Computern im Netzwerk, höchstens n² Verbindungen möglich sind.Da dies möglich ist, gib einen Graphen mir n² Verbindungen an.

Comments

Kannst du z.b. für 2 * n = 2 * 3 = 6 Computer aufzeigen, wie es da 9 Verbindungen gibt ?

Irgendwie fehlt mir da gerade die Vorstellungskraft warum 9.

---

So müsste das gehen ;)

---

Gleiche Frage in anderem Sachzusammenhang gibt es unter https://www.mathelounge.de/345682/sachaufgabe-zu-ungerichtetem-graphen.

Answer 1

> Da dies möglich ist, gib einen Graphen mir n² Verbindungen an.

Der vollständig bipartite Graph mit 2n Ecken.