Multiple choice

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

  1. I and II

  2. III and IV

  3. IV only

  4. II and IV
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Using the Havel-Hakimi theorem: A sequence is graphical if all degrees are non-negative, sum is even, and the sequence can be reduced to all zeros by repeatedly removing the largest element d and subtracting 1 from the next d elements. Sequence I (7,6,5,4,4,3,2,1): sum=32 (even). After reductions: 7×(6,5,4,4,3,2)→(5,4,3,3,2,1); 5×(4,3,3,2,1)→(2,2,1,1,1); 2×(2,1,1,1)→(1,0,0,1); sorting gives (1,1,0,0); 1×(1,0,0)→(0,-1,0) - NEGATIVE, so NOT graphical. Sequence II (6,6,6,6,3,3,2,2): 6×(6,6,6,3,3,2)→(5,5,5,2,2,1); 5×(5,5,2,2,1)→(4,4,1,1,0); sort: (4,4,1,1,0); 4×(4,1,1,0)→(3,0,0,-1) - NEGATIVE, so NOT graphical. Sequence III (7,6,6,4,4,3,2,2): 7×(6,6,4,4,3,2,2)→(5,5,3,3,2,1,1); 5×(5,3,3,2,1,1)→(4,2,2,1,0,0); 4×(2,2,1,0,0)→(1,1,-1,0,0) - NEGATIVE, NOT graphical? Wait, let me redo this more carefully... Actually for III: 7,6,6,4,4,3,2,2; remove 7: subtract from next 7: (5,5,3,3,2,1,2); sort: (5,5,3,3,2,2,1); remove 5: subtract from next 5: (4,2,2,1,1,1); sort: (4,2,2,1,1,1); remove 4: subtract from next 4: (1,1,0,0,1); sort: (1,1,1,0,0); remove 1: (0,0,0,0) - all zeros! So III IS graphical. Sequence IV (8,7,7,6,4,2,1,1): sum=36 (even, good). Remove 8: subtract from next 8 elements but only 7 exist - can't subtract 8 from 7 elements, so immediately NOT graphical. Also, in any simple graph, no vertex can have degree ≥ n-1. Here n=8, so max degree is 7. Having degree 8 is impossible. Therefore II and IV are NOT graphical. Answer is D.

Keep practicing — related questions