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?
A degree sequence $d_1,d_2,d_3\ldots d_n$ of non negative integer is graphical if it is a degree sequence of a graph. We now introduce a powerful tool to determine whether a particular sequence is graphical due to Havel and Hakimi Havel–Hakimi Theorem : → According to this theorem, Let $D$ be the sequence $d_1,d_2,d_3 \dots dn$ with $d_1 \geq d_2 \geq d_3 \geq \ldots d_n$ for $n \geq 2$ and $d_i \geq 0$. → If each $d_i = 0$ then $D$ is graphical → Then $D_0$ be the sequence obtained by: → Discarding $d_1$, and → Subtracting $1$ from each of the next $d_1$ entries of $D$. → That is Degree sequence $D_0$ would be : $d_2-1, d_3-1, \ldots , d_{d_1+1} -1, \ldots , d_n$ → Then, $D$ is graphical if and only if $D_0$ is graphical. Now, we apply this theorem to given sequences:
Hence, only option (I) and (III) are graphic sequence and answer is option-(D)
For this part-
"Option II) 6,6,6,6,3,3,2,2 → 5,5,5,2,2,1,2 ( arrange in ascending order) → 5,5,5,2,2,2,1 → 4,4,1,1,1,1 → 3,0,0,0,1 this type of graph can not possible so its not a graphical."
why we have 5,5,5,2,2,1,2 --> last 2 should be 1
@ Regina Phalange
in option 2) 6,6,6,6,3,3,2,2 here max degree is 6 so we apply theorem upto sixth position.
in option 1) 7,6,5,4,4,3,2,1 here max degree is 7 so we apply theorem upto seventh position..
hope u got it now .. :)
This might help ....
The answer is clearly D.
You can eliminate the last sequence i.e 4th one as... the total number of vertices is 8 and the maximum degree given is 8 too. which isn't possible at all. The maximum degree you can have out of 8 vertices is 7.
Now coming to the method for solving such questions is through Havel-Hakimi Algorithm.
you can implement it by following one simple video. Here it is. :)
D is correct ans
Gatecse
Please elucidate this really important...