Matematyka.pl

Udowodnij, że jeżeli graf prosty o n wierzchołkach ma więcej niż (n-1)(n-2)/2 krawędzi, to musi on być spójny.

hint.
\(\displaystyle{ {n \choose 2} = \frac{n(n-1)}{2}}\)

A czy mógłbyś bardziej to rozwinąć?
Byłbym wdzięczny.

Chodzi o to że gdy weźmiemy \(\displaystyle{ n-1}\) wierzchołków z tego grafu oraz \(\displaystyle{ {n-1 \choose 2}}\) krawędzi to powstanie graf pełny, zostaje nam tylko jeden wolny wierzchołek oraz co najmniej jedna krawędź więc graf musi być spójny