Register

GATE CSE 2010 | Question: 28

• edited by
18,550 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
User Avatar

7 Answers

0 votes
0 votes
ans d , 2nd and 4th not graphical using havell hakimi and maximum degree should not be equal to total no of vertices
User Avatar
0 votes
0 votes
For all options apply havel hakimmi theorem.

Also for degree sequence { 8,7,7,6,4,2,1,1}   there are 8 vertices and the max degree for 8 vertices can be 7  hence sequence is wrong as its mentioned that highest degree is 8

Therefore the answer is option D
User Avatar
–3 votes
–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
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

51 votes
51 votes
5 answers
1
gatecse asked Sep 21, 2014
11,503 views
GATE CSE 2010 | Question: 1
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 $\xi(S) = \xi(T)$, then $| S| = 2| T |$ $| S | = | T | - 1$ $| S| = | T | $ $| S | = | T| + 1$
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 ...
User Avatar
44 votes
44 votes
9 answers
3
Madhav asked Feb 14, 2017
17,553 views
GATE CSE 2017 Set 2 | Question: 23
$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 _________ .
$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 _________ .
User Avatar
15 votes
15 votes
3 answers
4
makhdoom ghaya asked Nov 14, 2016
1,848 views
GATE CSE 1987 | Question: 9c
Show that the number of odd-degree vertices in a finite graph is even.
Show that the number of odd-degree vertices in a finite graph is even.
User Avatar
Link Copied!