Question

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

Answer 1

The correct option is D II and IV

Havell-Hakimi algorithm can be used to check whether a given degree sequence is a graph or not.

The algorithm is
1. remove top node of the sequence.
2. Subtract "1" from as many nodes in remaining sequence as the degree of top node that was removed.
3. rearrange this sequence in non increasing order.
4. check if resulting sequence is a graph.
5. Proceed again to step 1.
If the given sequence is not a graph was see a violation in step 4, such as present negative degrees in the sequence. Others the algorithm will bottom out with a deep sequence consisting of only even number 1's and any number of 0's.

Now applying the algorithm to the deep sequences I, II, III and IV, one by one.

I. 7, 6, 5, 4, 4, 3, 2, 1
6, 5, 4, 4, 3, 2, 1 (Step 1)
5, 4, 3, 3, 2, 1, 0 (Step 2)
5, 4, 3, 3, 2, 1, 0 (Step 3)
Sequence is a graph (Step 4)
4, 3, 3, 2, 1, 0 (Step 1)
3, 2, 2, 1, 0, 0 (Step 2)
3, 2, 2, 1, 0, 0 (Step 3)
Sequence is a graph (Step 4)
2, 2, 1, 0, 0 (Step 1)
1, 1, 0, 0, 0 (Step 2)
1, 1, 0, 0, 0 (Step 3)
Sequence is a graph (Step 4)

Now, the algorithm ends, since the sequence has only 0's and even number of 1's.

The final sequence corresponds to following valid graph


Similarly for sequence II.

II. 6, 6, 6, 6, 3, 3, 2, 2
6, 6, 6, 3, 3, 2, 2 (Step 1)
5, 5, 5, 2, 2, 1, 2 (Step 2)
5, 5, 5, 2, 2, 2, 1 (Step 3)
Sequence is a graph (Step 4)
5, 5, 2, 2, 2, 1 (Step 1)
4, 4, 1, 1, 1, 1 (Step 2)
4, 4, 1, 1, 1, 1 (Step 3)
Sequence is a graph (Step 4)
4, 1, 1, 1, 1 (Step 1)
3, 0, 0, 0, 1 (Step 2)
3, 1, 0, 0, 0 (Step 3)
Sequence is a graph (Step 4)
1, 0, 0, 0 (Step 1)
0, -1, -1, 0 (Step 2)
0, 0, -1, -1 (Step 3)

The sequence is not a graph (Step 4), since negative degrees not possble in a valid graph.
So, algorithm ends.
II is cannot be the degree sequence of any graph.

Similarly we can show that III is degree sequence of some graph and IV is not a degree sequence of any graph.

So, option (d) is correct.