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.
Please help me out.
Best Answer
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.