A degree sequence d1,d2,d2. . . dn 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 sequence the d1,d2,d2. . . dn with d1 ≥ d2 ≥ d2 ≥ . . . dn for n≥ 2 and di ≥ 0.
→ Then D0 be the sequence obtained by:
→ Discarding d1, and
→ Subtracting 1 from each of the next d1 entries of D.
→ That is Degree sequence D0 would be : d2-1, d2-1, d3-1 . . . , dd1+1 -1 . . . , dn
→ Then, D is graphical if and only if D0 is graphical.
Now, we apply this theorem to given sequences:
option I) 7,6,5,4,4,3,2,1 → 5,4,3,3,2,1,0 → 3,2,2,1,0,0 → 1,1,0,0,0 → 0,0,0,0 so its graphical.
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.
Option III) 7,6,6,4,4,3,2,2 → 5,5,3,3,2,1,1 → 4,2,2,1,1,0 → 1,1,0,0,0 → 0,0,0,0 so its graphical.
Option IV) 8,7,7,6,4,2,1,1 , here degree of a vertex is 8 and total number of vertices are 8 , so it’s impossible, hence it’s not graphical.
Hence only option I) and III) are graphic sequence and answer is option-D