Degree sequence of graph

Question

Someone please solve it.

Comments

Minimum Edges required for graph to be connected $E_{min}= 9 $
Maximum Edges can be $E_{max} = \frac{10*9}{2} = 45$

1. $e= \frac{2*10}{ 2} = 10$, possible
2. $e= \frac{10}{ 2} = 5$,not possible because graph won’t be connected.
3. $e= \frac{3*10}{ 2} = 15$, possible

Hence answer will be B. 

---

it might be the case that $e_{min} \leq e \leq e_{max}$ and still we are unable to make simple connected graph.

For example, no. of vertices is $5$ and degree sequence is $(4,4,2,1,1)$

---

yes, you are right. Havel–Hakimi is the best method to solve this to get the correct answer every time.
thanks for pointing out the mistake:)

---

Not only Havel-Hakimi theorem, other methods are also there like Erdős–Gallai theorem.

Answer 1

There are two cases possible 

case:1(when noof vertices is odd)

If the noof vertices (with  degree of each vertex as 1) is odd then the graph is not even possible because the sum of degree of all the vertices is odd ( but using hand shaking lemma you can say that sum of degree is always even .) 

 

Case :2 (when noof vertices is even and all the vertices ga e degree 1) 

Using handshaking lemma you can find the noof edges . 

hand shaking lemma:  sum of degree of all verties = 2*(noof edges)

So from above question(option B) sum of degree of all vertices = 10  10=2*edges. Therefore e=5(noof edges)

But you know that a graph with n vertices to be connected the minimum noof edges is n-1 . So with n=10 the minimum edges is 9 but we got just 5 in option B . So option B was not possible . All the remaining are possible . 

NOTE ::

see the below link if you want to know , For a connected graph with n vertices the minimum noof edges is n-1 . 

https://stackoverflow.com/a/42600711