15,160 views

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?

1. $7, 6, 5, 4, 4, 3, 2, 1$
2. $6, 6, 6, 6, 3, 3, 2, 2$
3. $7, 6, 6, 4, 4, 3, 2, 2$
4. $8, 7, 7, 6, 4, 2, 1, 1$
1. I and II
2. III and IV
3. IV only
4. II and IV

Which of the following sequences can not be the degree sequence of any graph?

that’s what the question is also asking for right?

Yes

ans d , 2nd and 4th not graphical using havell hakimi and maximum degree should not be equal to total no of vertices
For all options apply havel hakimmi theorem.

Also for degree sequence { 8,7,7,6,4,2,1,1}   there are 8 vertices and the max degree for 8 vertices can be 7  hence sequence is wrong as its mentioned that highest degree is 8

Therefore the answer is option D
by
A is the correct option step1:arrange the degree in descending order Step2:consider the 1st element and decrease each element by 1 Step3:continue this for all elements Step4:the option having even number of 1s is the correct option

### 1 comment

Answer is D) try to do it with Havell Hakimmi theorem when you  wil apply theorem on choice II and IV

in II you will left with vertex one of degree 3 ie. 3,0,0 which is not possible