Sachaufgabe zu ungerichtetem Graphen

Question

Fritz hat ein Netzwerk Konstruiert , wobei es

im Netz  keine drei Leute gibt , die sich alle direkt kennen.
(es soll maximal viele Verbindungen geben)

Nun ist zu zeigen , dass es bei 2n Personen ( Fritz mitein berechnet) nicht mehr als n^2 Verbindungen geben kann.

Desweiteren soll gezeigt werden , dass es für jedes natürliche n  ein Netz mit n^2 Verbindungen gibt welches die Bedingung erfüllt

Comments

Gleiche Frage in anderem Sachzusammenhang gibt es unter https://www.mathelounge.de/346123/logik-ratsel-mit-graphen-und-kombinationsmoglichkeiten.

Answer 1

> im Netz  keine drei Leute gibt , die sich alle direkt kennen.

Das heißt der kleinste Kreis hat mindestens die Länge 4.

> Desweiteren soll gezeigt werden , dass es für jedes natürliche n  ein Netz mit n² Verbindungen gibt welches die Bedingung erfüllt

Der vollständig bipartite Graph K_n,n erfüllt obige Bedingung.

Comments

aber wie wird hierbei gezeigt , dass es bei 2n Personen nicht mehr als n² Verbindungen geben kann und

  es für jedes natürliche n  ein Netz mit n² Verbindungen gibt ???