edited by
18,408 views
40 votes
40 votes

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
edited by

7 Answers

Best answer
46 votes
46 votes

A degree sequence $d_1,d_2,d_3\ldots d_n$ 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 the sequence $d_1,d_2,d_3 \dots dn$ with $d_1 \geq d_2 \geq d_3 \geq \ldots d_n$ for $n \geq 2$ and $d_i  \geq 0$.
→ If each $d_i = 0$ then $D$ is graphical
→ Then $D_0$ be the sequence obtained by:
→ Discarding $d_1$, and
→ Subtracting $1$ from each of the next $d_1$ entries of $D$.
→ That is Degree sequence $D_0$ would be : $d_2-1, d_3-1, \ldots  , d_{d_1+1} -1, \ldots , d_n$
→ Then, $D$ is graphical if and only if $D_0$ 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 it is graphical.
  2. $6,6,6,6,3,3,2,2 \rightarrow 5,5,5,2,2,1,2$ ( arrange in descending order) $\rightarrow 5,5,5,2,2,2,1 \rightarrow 4,4,1,1,1,1 \rightarrow 3,0,0,0,1$ we cannot continue to get all $0's$, so it is not 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 it is graphical.
  4. $8,7,7,6,4,2,1,1$, here degree of a vertex is $8$ and total number of vertices are $8$,  which is impossible, hence it is not graphical.


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

edited by
25 votes
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. :)

edited by
0 votes
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
Answer:

Related questions

51 votes
51 votes
5 answers
1
gatecse asked Sep 21, 2014
11,366 views
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with ...
44 votes
44 votes
9 answers
3
Madhav asked Feb 14, 2017
17,292 views
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
15 votes
15 votes
3 answers
4
makhdoom ghaya asked Nov 14, 2016
1,793 views
Show that the number of odd-degree vertices in a finite graph is even.