0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – laura Oct 4 '17 at 7:44
  • $\begingroup$ am i correct @Jorge? $\endgroup$ – laura Oct 5 '17 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.