Graphs

Question

A sequence d = is graphic if there is a simple non-directed graph with degree sequence d then which one of the following sequences is graphic?

a) (2, 3, 3, 4, 4, 5) b) (1, 3, 3, 3) c) (2, 3, 3, 4, 5, 6, 7) d) (2, 3, 3, 3, 3)

Comments

Option a is not possible,since sum of all the degree comes out to be odd.

Option c is also not possible,since there are 7 vertices and  maximum degree of a vertex can be 6.

Now we are left with option b and d.We can use Havel Hakimi algorithm.

for Option b

Rearranging in descending order 3 3 3 1--> 2 2 0 -->1 -1

this is not possible hence not graphic.

For Option D,after rearranging ,

3 3 3 3 2 -->2 2 2 2 -->1 1 2 (arrange in descending)

2 1 1--> 0 0 which is graphical.

Hence answer should be D

Answer 1

Since degree of vertices is given let us first calculate Sum of degree of vertices.

Option A) $\sum d(2,3,3,4,4,5)=21$

Option B) $\sum d(1,3,3,3)=10$

Option C) $\sum d(2,3,3,4,5,6,7)= 30$

Option D) $\sum d(2,3,3,3,3)=14$

Option A is ruled out sum of degree of vertices must be even

Option C ruled out Maximum degree cannot be 7 in 7 vertex simple graph.

Arrange B in Non decreasing order d(3,3,3,1)

Now if we remove one vertices degree of other will decrease by 1

d(2,2,0)

similarly

d(1,-1) degree cannot be negative so option C is also not possiable

D) Arranging it in non decreasing order d(3,3,3,3,2)

d(2,2,2,2)

d(1,1,2)=d(2,1,1)

d(0,0)

Option D is answer