GO Classes CS Test Series | Mock GATE | Test 4 | Question: 49

Answer 1

A: Not Possible
A tree with $n$ vertices has $n-1$ edges, hence, the sum of the degrees of all the vertices is $2(n-1).$
https://youtu.be/JFoMdTRNr3w?t=751

B: Possible
Make a forest with $5$ components (Any forest will work)

C: Not possible
The minimum number of edges in a simple graph with $n$ vertices and $k$ connected components is $n-k.$
https://youtu.be/JFoMdTRNr3w?t=3842  

D: Not possible
https://youtu.be/JFoMdTRNr3w?t=875
The maximum number of edges in a simple graph with $n$ vertices and $k$ connected components is $n-1.$
https://youtu.be/JFoMdTRNr3w?t=310

Comments

A simple graph with n vertices and k components can have atmost ( n-k)(n-k+1)/2 edges.

---

So, is it $(n-1)$ or $(n-k)(n-k+1)/2$ ?

---

@pranavbhosle_ A simple graph with  k component range min to max is 

(n-k) <=e <= (n-k)(n-k+1)/2

---

D is for trees' that is a type of forest graph

Answer 2

Thanks to @Deepak Poonia sir

ANSWER = B 

Comments

Thanks man!!!

Answer 3

You can verify all the options using this theorem

Theorem: A simple graph with n vertices and k components can have 

n-k <= no.of edges <= ( n-k)(n-k+1)/2

Comments

@vinayedula,does this formula works on K=1 ,when no of components is equal to 1.

it is not working on option d,where k=1.

for option d,

According to this formula,minimum edges are 8

& maximum edges are 36

 

---

Option D is asking about one simple graph only(one component) as they did not mentioned number of components explicitly. So with 9 vertices maximum number of edges will be there when the graph is complete graph(number of edges 36,), but obviously it has cycles.

And for maximum number of edges without any cycle, the graph has to be a tree. So n-1=9-1=8 edges.( Sorry for my bad English..)