# Number of edges in a graph with N vertices and K components

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?

• There's always some question of whether graph theory is on-topic or not. But extremal graph theory (how many edges do I need in a graph to guarantee it contains some structure? What's the most edges I can have without that structure?) seem to be quite far from computation, to me. Jan 26, 2018 at 14:15

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)
the first term counts minimum edges for first $f'$ components which have 1 vertex extra and the second term is for the remaining components.