# Minimum number of edges in a graph with $n$ vertices and $k$ connected components

## Question

Minimum Number of edges in a graph with $n$ vertices and $k$ connected components.

I know it is already posted here,still i am posting this because I want to calculate it using my own way and I am stuck.

## My Approach

As we are given $k$ components, in all $k-1$ components, I will put only $1$ vertex each and in the last component i.e $k^{th}$ component , i will put maximum edge.

Number of vertices left in $k^{th}$ component=$n-(k-1)$

So maximum number of edges possible in $k^{th}$ component$$=\binom{n-(k-1)}{2}$$

$$=\frac{(n-(k-1))*(n-(k-1)-1)}{2}$$

$$=\frac{(n-k+1)*(n-k)}{2}$$

I am done for maximum number of edges , but i am not getting how to solve for
minimum number of edges.

the empty graph on $n$ vertices has $n$ components, each edge reduces the number of components by at most $1$.
Therefore we need to add at least $n-k$ edges, and as long as we don't form any cycles ( in other words only add edges between unconnected edges) $n-k$ edges will be enough.
• you mean in $k-1$ components , put $1$vertex each(i.e $0$ edges each ) and in the $k^{th}$ component,we have $n-(k-1)$ vertex so to make it connected we will need $(n-(k-1))-1$ edges =$n-k+1-1$=$n-k$ edges ? – laura Oct 4 '17 at 7:44