Witam.
Do poniższego zadania mam zapisane rozwiązanie, jednak nie wyjaśnia mi ono wszystkiego, dlatego proszę o pomoc.
Udowodnij, że jeśli \(\displaystyle{ e(G)> {{|G|-1} \choose 2}}\), to graf \(\displaystyle{ G}\) jest spójny.
Moje notatki zawierają następujący dowód:
Przypuśćmy, że \(\displaystyle{ e(G)>{{|G|-1} \choose 2}}\), ale graf \(\displaystyle{ G}\) jest niespójny (dowód przez zaprzeczenie).
Jedna składowa ma \(\displaystyle{ k}\) wierzchołków, druga \(\displaystyle{ n - k}\) (cały graf ma \(\displaystyle{ n}\) wierzchołków). \(\displaystyle{ k=1, 2, ..., n-1}\)
\(\displaystyle{ e(G) \le {k \choose 2}+{{n-k} \choose 2}= \frac{k(k-1)}{2} + \frac{(n-k)(n-k-1)}{2}=k^2 - nk + \frac{n(n-1)}{2}}\)
Do tego momentu wszystko rozumiem. Problem zaczyna się tutaj:
dla \(\displaystyle{ k=1}\):
\(\displaystyle{ {1 \choose 2} + {{n-1} \choose 2} = {{n-1} \choose 2}}\)
dla \(\displaystyle{ k=n-1}\):
\(\displaystyle{ {{n-1} \choose 2}+{1 \choose 2}={{n-1} \choose 2}}\)
Widzę, że jest to podstawienie do mojej nierówności \(\displaystyle{ e(G)>{{|G|-1} \choose 2}}\) i oznacza to, że taka sama ilość krawędzi jest wtedy gdy w danej składowej jest 1 lub n-1 wierzchołków, jednak jak to przeczy temu, że graf jest niespójny, nie mogę się domyślić. Proszę o rozjaśnienie umysłu.