The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
3.3k views

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?

  1. $7, 6, 5, 4, 4, 3, 2, 1$
  2. $6, 6, 6, 6, 3, 3, 2, 2$
  3. $7, 6, 6, 4, 4, 3, 2, 2$
  4. $8, 7, 7, 6, 4, 2, 1, 1$

 

  1. I and II
  2. III and IV
  3. IV only
  4. II and IV
asked in Graph Theory by Boss (18k points)
edited ago by | 3.3k views
0
Havel-Hakimi Algorithm.

5 Answers

+13 votes
Best answer

A degree sequence $d1,d2,d2. . . dn$ of non negative integer is graphical if it is a degree sequence of a graph. We now introduce a powerful tool to determine whether a particular sequence is graphical due to Havel and Hakimi

Havel–Hakimi Theorem :

→ According to this theorem, Let $D$ be sequence the $d1,d2,d2. . . dn$ with $d1 \geq d2 \geq d2 \geq . . . dn$ for $n \geq 2$ and $di  \geq 0$.
→ Then $D0$ be the sequence obtained by:
→ Discarding $d1$, and
→ Subtracting $1$ from each of the next $d1$ entries of $D$.
→ That is Degree sequence $D0$ would be : $d2-1, d2-1, d3-1 . . . , dd1+1 -1 . . . , dn$
→ Then, $D$ is graphical if and only if $D0$ is graphical.

Now, we apply this theorem to given sequences:

  1. $7,6,5,4,4,3,2,1 \rightarrow 5,4,3,3,2,1,0 \rightarrow 3,2,2,1,0,0 \rightarrow 1,1,0,0,0 \rightarrow 0,0,0,0$ so its graphical.
  2. $6,6,6,6,3,3,2,2 \rightarrow 5,5,5,2,2,1,2$ ( arrange in ascending order) $\rightarrow 5,5,5,2,2,2,1 \rightarrow 4,4,1,1,1,1 \rightarrow 3,0,0,0,1$ this type of graph can not possible  so its not a graphical.
  3. $7,6,6,4,4,3,2,2 \rightarrow 5,5,3,3,2,1,1 \rightarrow 4,2,2,1,1,0 \rightarrow 1,1,0,0,0 \rightarrow 0,0,0,0$ so its graphical.
  4. $8,7,7,6,4,2,1,1$ , here degree of a vertex is $8$ and total number of vertices are $8$ , so it’s impossible, hence it’s not graphical.


Hence only option (I) and (III) are graphic sequence and answer is option-(D)

answered by Active (4.1k points)
edited ago by
0
You have not applied the algorithm correctly while tracing it for option 2...(5,5,5,2,2,2,1)-> (4,4,1,1,1,1)
+1
yes now edited.
0

For this part-

"Option II) 6,6,6,6,3,3,2,2 → 5,5,5,2,2,1,2 ( arrange in ascending order) → 5,5,5,2,2,2,1 → 4,4,1,1,1,1 → 3,0,0,0,1 this type of graph can not possible  so its not a graphical."

why we have  5,5,5,2,2,1,2  --> last 2 should be 1

+1

@ Regina Phalange

in option 2) 6,6,6,6,3,3,2,2 here max degree is 6 so we apply theorem upto sixth position.

in option 1) 7,6,5,4,4,3,2,1 here max degree is 7 so we apply theorem upto seventh position..

hope u got it now .. :) 

0

This might help ....

 

 

 

+25 votes

The answer is clearly D.

You can eliminate the last sequence i.e 4th one as... the total number of vertices is 8 and the maximum degree given is 8 too. which isn't possible at all. The maximum degree you can have out of 8 vertices is 7.

Now coming to the method for solving such questions is through Havel-Hakimi Algorithm.

you can implement it by following one simple video. Here it is. :)

answered by Boss (19.7k points)
edited by
0
YES (D) option is the correct.!!
0
Is this in the syllabus?
0
a big yes
0
We eliminated option D only because the graph is a simple graph. Were it a non-simple graph, then D won't be wrong, right?
+4 votes

D is correct ans

answered by Active (4.2k points)
0 votes
I) 5433210 = > 322100=> 11000=> 0000 so option i  correct eliminates A

ii)66663322 = > 555221 =>44110=>3000 so not graphic sequence eliminates B and C so D is answer
answered by Loyal (6.4k points)
–3 votes
A is the correct option step1:arrange the degree in descending order Step2:consider the 1st element and decrease each element by 1 Step3:continue this for all elements Step4:the option having even number of 1s is the correct option
answered by Boss (14.1k points)
+1
Answer is D) try to do it with Havell Hakimmi theorem when you  wil apply theorem on choice II and IV

 

in II you will left with vertex one of degree 3 ie. 3,0,0 which is not possible


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,527 questions
42,803 answers
121,618 comments
42,166 users