What is the possible biggest and the smallest number of edges in a graph with N vertices and K components?
I think that the smallest is (N-1)K. The biggest one is NK. Is this correct? I think it also may depend on whether we have and even or an odd number of vertices?
Think of the extreme case when all the components of the graph except one have just one vertex. This is the case which will have the most no. of edges. We can prove it by contradiction as follows:
Suppose there were two strongly connected components having $m$ and $n$ vertices where $m < n$. Now if you remove a vertex from the one having $m$ vertices and add it to the other component, then effectively you have removed $m-1$ edges from the first graph and added $n $ edges to the second graph. So, there is a net gain in the number of edges.
So the maximum edges in this case will be $\dfrac{(n-k)(n-k+1)}{2}$.
As for the minimum case, since we have seen that distributing the edges with uniformity among the graphs leads to an overall minimization in their number, therefore first divide all the $n$ vertices into $k$ components to get the number of vertices in each component as $n/k$. We will still be left with $n\mod k = f'$ vertices. Let's call $\Biggl\lfloor{\dfrac{n}{k}}\Biggr\rfloor$ = $f$. Then, the $k$ components each already have $f$ vertices with them. Now , give away $1$ vertex each to first $f'$ components. This completes our vertex distribution.
So, total edges$ = (f + 1 - 1)*f' + (f-1)*(f - f')$ (because we have minimum of $x-1$ edges for $x$ available vertices)
where
the first term counts minimum edges for first $f'$ components which have 1 vertex extra and the second term is for the remaining components.
