LetG VE be a graph with V v1v2vn Its degree sequence is th

LetG = (V,E) be a graph with V = {v1,v2,...,vn}. Its degree sequence is the list of the degrees of its vertices,arranged in non-increasing order. That is,the degree sequence of G is(degG(v1),degG(v2),...,degG(vn)) with the vertices arranged such that degG(v1) degG(v2) ··· degG(vn). Below are ve sequences of integers (along with n,the number of integers in the sequence). Identify

• the one sequence that cannot be the degree sequence of any graph;

• the two sequences that could be the degree sequence of a planar graph;

• the one sequence that could be the degree sequence of a tree;

• the one sequence that is the degree sequence of a neulerian graph;and

• the one sequence that is the degree sequence of a graph that must be hamiltonian.

Explain your answers. (Note that one sequence will get two labels from above.)

a) n = 10: (4,4,2,2,1,1,1,1,1,1)

b) n = 9: (8,8,8,6,4,4,4,4,4)

c) n = 7: (5,4,4,3,2,1,0)

d) n = 10: (7,7,6,6,6,6,5,5,5,5)

e) n = 6: (5,4,3,2,2,2)

Solution

Solutiion:

(a) n=10: (4,4,2,2,1,1,1,1,1,1)

This sequence has at least two vertices of degree 1. We know that a tree has minum of two leaves. So we can say that this sequence is a degree sequence of tree.

It could also be plannar as it has 24 edges.(as 4+4+2+2+1+1+1+1+1+=18/2 = 9< 3(10)-6 =24)

(b) n =9 : (8,8,8,6,4,4,4,4,4)

In this sequence all degrees are even. The conditions for a degree sequence to be Eulerian is, the degrees of the sequence are even. So it is a Eulerian sequnce

(c) n =7: (5,4,4,3,2,1,0)

Here, there are 3 odd degree vertices. A graph can not have an odd number vertices of odd degree. So it is the sequence of no graph.

(d) n= 10:(7,7,6,6,6,6,5,5,5,5)

The graph of the sequence is not plannar as 7+7+6+6+6+6+5+5+5+5 =58/2 = 29> 3(10)-6 =24 edges.

Dirac\'s theorem on Hamiltonian cycles: a n vertex with each vertex has at least n/2 must a Hamiltonian cylce.

So the graph is Hamiltonian as 10/2 =5

(e)n =6: (5,4,3,2,2,2).

Here 18/2 = 9 < 3(6) -6 =12 .So the sequence can be plannar.

   2