GATE previous years with little Modification

Question

The Minimum number of possible edges in an undirected graph with n vertices and k components is ______

Comments

n-k?

---

Yes , me too got the same answer , but i was not very sure about that..

I think the idea is quite same as that of finding Maximum Number of Edges.

The only difference is that there we were trying to make a complete graph with n-(k-1) vertices, but here we should go for Spanning trees, 

so the answer is n-k..

 

@arvin sir, Is there anything illogical in my concept?

---

as they have asked for minimum and  n-k < n-(k-1) :

so here also we have to consider n-k .

.

yes i too saw it on many sites and they had n-(k-1), i am unable to understand why they put that...

---

http://mathworld.wolfram.com/EmptyGraph.html

u also have to write that we cant have null graph . because according to your question we can have null graph then min is 0 

---

@Deepanshu brother if we have null grpahs also than also in that case n-k is valid... n vertices and n components = n-n = 0 edges...

---

so according to u if we have a null graph of 5 vertex means it has 5 components

---

yes @Deepanshu every diconnected set of vertices will be a component.

---

As we know the maximum number of edges with n vertices and k component is 

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

But we consider minimum then the answer will be zero.

Because of n = k. then It will be zero.( Forming Null graph.)

---

no, it will be 0 only when n=k.. for other cases it will be n-k.. as the number of edges will be dependent on the number of components...

we cannot assume it to be null graph everytime..