Ich denke, dass man das für einfache Graphen (ohne Mehrfachkanten und Schleifen) zeigen soll. Ansonsten ist es nämlich nicht richtig, siehe zum Beispiel der Graph mit 3 Knoten und 2 > (2 über 2) = 1 Kanten, wobei sich die beiden Kanten jeweils zwischen denselben Knoten befinden. Dann ist der dritte Knoten unverbunden, damit der Graph nicht zusammenhängend.
Für einfache Graphen mit n Knoten gibt es maximal (n über 2) Kanten, das kann man sich leicht kombinatorisch überlegen: jede Kante verbindet zwei Knoten, dabei ist eine Kante zwischen Knoten A und Knoten B dasselbe wie eine Kante zwischen Knoten B und Knoten A. Eine Kante ist also eindeutig bestimmt, wenn man die beiden Knoten, die sie verbindet aus den n möglichen Knoten ausgewählt hat.
Nehmen wir nun an, der Graph wäre unzusammenhängend. Das hieße, es gäbe zwei Teile des Graphen mit k und n-k Knoten, die also jeweils zusammengenommen maximal (k über 2) und (n-k über 2) Knoten haben. Damit lautet die maximal Knotenzahl eines solchen unzusammenhängenden einfachen Graphen
$$q_\text{max}(k) = \begin{pmatrix} k \\ 2\end{pmatrix} +\begin{pmatrix} n-k \\ 2\end{pmatrix}$$
hierbei muss die Definition (1 über 2) = 0 benutzt werden. Die Behauptung ist nun
$$q_\text{max}(k) \leq \begin{pmatrix}n-1\\2\end{pmatrix}$$
für k = 1, 2, ..., n-1.
Diese Behauptung ist äquivalent zu
$$ k(k-1) + (n-k)(n-k-1) \leq (n-1)(n-2)$$
und nach Umformung zu
$$ k^2 + n \leq kn + 1.$$
Betrachtet man beide Seiten für festes n als Funktionen von k, dann beschreibt die linke Seite eine nach oben offene Parabel und die rechte eine Gerade mit Steigung n. Es lässt sich leicht nachrechnen, dass beide Seiten für k = 1 und für k = n-1 (die natürlich eigentlich dieselbe Situation beschreiben) identisch sind - damit folgt direkt die Richtigkeit der Aussage.
Das ergibt auch automatisch die Fälle, die die Ungleichung saturieren: für einen Graphen mit n Knoten, besitzt der Graph mit einem isolierten Knoten bei dem alle anderen Knoten jeweils miteinander verbunden sind genau (n-1 über 2) Knoten.
