Vollständige Graphen
Da in einem Graphen der Ordnung n jede Ecke höchstens n − 1 Nachbarn haben kann, ist die konstante Folge n − 1, …, n − 1 der Länge n die größte mögliche Gradfolge eines Graphen der Ordnung n. Nach dem Satz über die Gradsumme ist in diesem Fall n(n − 1) = 2|K|. Wir definieren hierzu:
Definition (vollständig)
Ein Graph G = (E, K) heißt vollständig, falls je zwei verschiedene Ecken von E durch eine Kante verbunden sind.
Die vollständigen Graphen der Ordnung n sind genau die Graphen mit maximaler Größe |K| = n (n − 1)/2 und maximaler Gradfolge n − 1, …, n − 1.
Definition (die Graphen Kn)
Sei n ≥ 1. Dann ist der kanonische vollständige Graph Kn definiert durch
Ecken von Kn: 1, …, n Kanten von Kn: ij mit 1 ≤ i < j ≤ n
Die vollständigen Graphen K1, …, K9