I am trying to solve the following problem:
Let $G$ be a graph on $n$ vertices. Assume $G$ is disconnected such that any connected component has size $\geq K$. Show that $|E(G)| \leq \binom{k}{2} + \binom{n-k}{2}$.
The first term is kind of obvious. Every $k$-size connected component could be at most a clique and a clique has $\binom{k}{2}$ edges. That would leave us with $n-k$ vertices in the components that can be connected between them (only in the components though). How can we prove that this number is $\binom{n-k}{2}$? I thought about splitting this term into $n_1, n_2, \dots, n_m$ vertices for the $m$ connected components such that their sum is $n-k$ and then use properties of the binomial coefficients but I couldn't prove an equality between the second terms.
Any hints/ideas about that or another direction?
A connected component of $m$ vertices contains at most $\binom{m}{2}$ edges, and there at most $\binom{n-m}{2}$ edges outside it. Hence $|E(G)|\leq\binom{m}{2}+\binom{n-m}{2}$. Because $n>m\geq k$ it follows that $$\binom{m}{2}+\binom{n-m}{2}=\frac{1}{2}(n^2+(2m-2n+1)m)\leq\frac{1}{2}(n^2+(2k-2n+1)k)=\binom{k}{2}+\binom{n-k}{2}.$$