The degree sequence of a graph is the list of vertex degrees

The degree sequence of a graph is the list of vertex degrees written in nonincreasing order. A graphic sequence is a list on nonnegative numbers that is the degree sequence of some simple graph. (a) Is (4, 3, 2, 2, 1, 1, 1, 0) graphic? Justify our answer. (b) Is (4, 3, 3, 2, 1, 1, 1, 0) graphic? Justify our answer. (c) Is (5, 4, 3, 3, 1) graphic? Justify your answer.

Solution

We apply Havel Haeikimi algorithm for this :

(a) 4, 3,2,2,1,1,1,0 .....

2,1,1,0,1,1,0....Remove 4 and subtract 1 to 4 numbers below

2,1,1,1,1,0,0....Order

0,0,1,1,0,0..Remove 2 and subtract 1 to 2 numbers below

1,1,0,0,0,0....Order

0,0,0,0,0....Remove 1 and subtract 1 to 1 number below

As we get all 0 in end and so the given sequence is graphic

(b) 4,3,3,2,1,1,1,0

2,2,1,0,1,1,0....Remove 4 and subtract 1 to 4 numbers below

2,2,1,1,1,0,0...Order

1,0,1,1,0,0..Remove 2 and subtract 1 to 2 numbers below

1,1,1,0,0,0...Order

0,1,0,0,0..Remove 1 and subtract 1 to 1 number below

1,0,0,0,0....Order

-1,0,0,0....Remove 1 and subtract 1 to 1 number below

Hence the given sequence is not graphic

(c) 5,4,3,3,1

This is not graphic as total number of vertices is 5 and maximum degree is also 5 here which is not possible