Proving an inequality when a graph is not connected

Question

Suppose $G = (V, E)$ is not connected. Prove that $ |E| ≤ \frac{(|V | − 1)(|V | − 2)}{2}$?

I've tried using the handshaking lemma, but I'm not sure how I can use the fact that G is not connected to achieve this result.

Answer 1

Since it is not connected there are two nonempty subsets $A$ and $B$ of vertices in graph, such that there is no edge between them. So we have at most $${a\choose 2}+{b\choose 2} = {a^2+b^2-a-b\over 2}$$ edges in graph where $a=|A|$ and $b=|B|$ and $a+b = n=|V|$. Now you can check that

$$ {a^2+b^2-a-b\over 2}\leq {(a+b)^2-3(a+b)+2\over 2}$$

is true.

Answer 2

Hint: In view of the hand-shaking lemma applied to each connected component, you have

$$ |E_k| \le \binom{|V_k|}{2} $$

where $|E_k|$ is the number of edges and $|V_k|$ that of vertices of the $k$-th connected component. Sum over all possible connected components and try to find a suitable upper bound for your sum.