The degree sequence of a graph is the sequence of the degree

The degree sequence of a graph is the sequence of the degrees of the vertices of the graph in nonincreasing order. Which of the following sequences could be degree sequences of a simple graph?? For those that are, draw a graph with that degree sequence. For those that are not, say why not. 5, 4, 3, 2, 1, 0 3, 3, 3, 3, 3, 3 3, 3, 3, 2, 2, 2 1, 1, 1, 1, 1, 1 6, 5, 4, 3, 2, 1

Solution

none of the sequnces are graphical. The sequnces are not graphical because of following reasons

a) 5,4,3,2,1,0

Here we have total of 6 vertices.So from first vertex there must be an edge to all the other vertices if the degree has to be 5 .Then we cannot get 0 on the degree sequnce.

hence not graphical

b)3,3,3,3,3,3

in the graph one of the vertex will have a loop. hence not simple

c)3,3,3,2,2,2

not graphical. For a sequnce to be graphical, number of odd degree must be even.here 3 comes odd number of times.Hence not graphical.

d) 1,1,1,1,1,1

the sequence is not graphical.This is because all vertices cannot have degree one

e)6,5,4,3,2,1

not graphical.

For a sequence with n vertices to be graphical degree of each vertex must be less than or equal to 5.

here 6 occur as degree.

So not graphical