I am trying to prove the following result: let $G=(V,A)$ be a graph with $p$ connected components. Prove that
$$|V|-p\leq |A|\leq \binom{|V|-p+1}{2}$$
I have shown that if $G$ is a connected graph with $n$ vertices and $m$ edges, then $m\geq n-1$.
What I have tried to do is: as we have shown above, $|A|\geq |V|-1$, as there is at least one connected component (the graph $G$ itself), $|V|-p$ will also be true!
$$\binom{|V|-p+1}{2}=\textrm{ number of edges of the graph } K_{|V|-p+1}$$
$$|V|-p\leq |A|$$
It is clear that at most, $\binom{|V|-p+1}{2}$ can be equal to $\binom{n}{2}=m(K_n)$ since there is at least one connected component, the graph $G$ itself.
I don't know how to continue.
Best Answer
HINT: You know that $|A|\ge|V|-1$ for a connected graph, but you cannot apply that result to $G$ here unless $p=1$, so that $G$ is connected. You can, however, prove the first inequality by applying that result to each of the $p$ components of $G$.
You know that $\binom{|V|-p+1}2$ is the number of edges in $K_{|V|-p+1}$, but that graph is not $G$ (unless $p-1$). In order to apply that result here, you will have to prove that $G$ cannot have any more edges than the graph $K_{|V|-p+1}$ has. If you add $p-1$ isolated vertices to $K_{|V|-p+1}$, you get a graph $G_0$ with $|V|$ vertices and $p$ connected components. You can prove the second inequality by showing that among all graphs with $|V|$ vertices and $p$ connected components, $G_0$ is the one with the largest number of edges; I’ll sketch one way to do.
Let $G$ be any graph with $|V|$ vertices and $p\ge 2$ connected components. Let $C_1$ and $C_2$ be two of the components of $G$, with $n_1$ and $n_2$ vertices, respectively; $C_1$ and $C_2$ have altogether at most $\binom{n_1}2+\binom{n_2}2$ edges. (Why?) Replace $C_1$ by an isolated vertex and $C_2$ by $K_{n_1+n_2-1}$, and show that the resulting graph has at least as many edges as $G$ and still has $|V|$ vertices and $p$ components. Show that by performing this operation a finite number of times you can convert $G$ to $G_0$, and conclude that $G$ has at most as many edges as $G_0$.