Project ForgeThe 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
- AI and II
- BIII and IV
- CIV only
- II and IV
Explanation
IV is immediately invalid: with only 8 vertices, the maximum possible degree is 7 (n-1), but IV has a vertex of degree 8. Applying Havel-Hakimi to II (6,6,6,6,3,3,2,2): reducing repeatedly eventually forces a negative remaining degree, so II is not graphical. I and III both reduce cleanly to all-zeros via Havel-Hakimi, confirming they ARE valid degree sequences. So the non-graphical sequences are II and IV.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.