Eine Extremalaufgabe aus der Graphentheorie. (Q2584278)

Ein Graph heißt vollständig, falls je zwei seiner Knotenpunkte durch genau eine Kante verbunden sind. Mit \(D (n, k)\) bezeichnen wir einen Graph mit \(n\) Knotenpunkten, der folgendermaßen definiert wird: \(n\) Punkten sei eine und nur eine der natürlichen Zahlen \(1, 2,\dots, n\) zugeordnet, und es seien genau diejenigen Punkte untereinander verbunden, denen mod \((k - 1)\) inkongruente Zahlen zugeordnet sind. -- Die Note enthält die folgenden Sätze: Unter den Graphen mit \(n\) Knotenpunkten, die keinen \(k\)-punktigen vollständigen Graphen enthalten, hat der Graph \(D (n, k)\) und nur dieser die maximale Kantenzahl. Die Kantenzahl des Graphen \(D(n,k)\) beträgt \(\dfrac 12 (k - 2)(k - 1)^{-1} (n^2 - r^2) + \binom r2\), wo \(r\) der Rest der Teilung von \(n\) durch \(k - 1\) ist. Eine zweite Extremaleigenschaft des Graphen \(D (n, k)\) ist folgende: Die kleinste Teilmenge der Kanten des \(n\)-punktigen vollständigen Graphen \(G\), die aus jedem Äxpunktigen vollständigen Graphen von \(G\) eine Kante enthält, liefert die Komplementärmenge von \(D (n, k)\). -- Der letzte Satz bezieht sich auf unendliche Graphen und lautet: Hat ein Graph mit abzählbar unendlichen Knotenpunkten die Eigenschaft, daß es in jeder Gruppe von \(d\) Knotenpunkten (wo \(d > 1\) eine feste Zahl ist) zwei solche Knotenpunkte gibt, die durch eine Kante verbunden sind, so hat der Graph einen vollständigen unendlichen Teilgraph.