The degree sequence of a simple graph is the sequence of the degrees of the…
2010
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?
I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1
- A.
I and II
- B.
III and IV
- C.
IV only
- D.
II and IV
Attempted by 160 students.
Show answer & explanation
Correct answer: D
Correct answer: the sequences 6, 6, 6, 6, 3, 3, 2, 2 and 8, 7, 7, 6, 4, 2, 1, 1 cannot be degree sequences.
6, 6, 6, 6, 3, 3, 2, 2 fails the Erdős–Gallai inequality for k = 4: the sum of the first four degrees is 24, while the right-hand side equals 4·3 + (min(3,4)+min(3,4)+min(2,4)+min(2,4)) = 12 + 3 + 3 + 2 + 2 = 22, so 24 > 22 and the sequence is not graphical.
8, 7, 7, 6, 4, 2, 1, 1 is impossible because in a simple graph on 8 vertices the maximum possible degree is 7, so a degree of 8 cannot occur.
Quick notes on the other sequences: 7, 6, 5, 4, 4, 3, 2, 1 is graphical (Havel-Hakimi reduces it to all zeros). 7, 6, 6, 4, 4, 3, 2, 2 satisfies the Erdős–Gallai inequalities and is graphical.
A video solution is available for this question — log in and enroll to watch it.