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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer?

Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity

Open App

GATE Exam > GATE Questions > The degree sequence of a simple graph is the ...

Join the Discussion on the App

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?

a)
I and II
b)
III and IV
c)
II and IV
d)
IV only

Correct answer is option 'C'. Can you explain this answer?

FREE This question is part of

Test: Graph Theory- 2

Attempt Test

Attempt this Test

Verified Answer

The degree sequence of a simple graph is the sequence of the degrees o...

Havel Hakimi theorem:

Arrange the degree of vertices in descending order

eg. d₁, d₂, d₃... d_n

Discard d₁and subtract '1' from the next 'd_i' degrees

Ex:3,2,2,1,1

discard degree 3 and subtract one from the next highest 3 degrees. It means removing a vertex of degree 3 that refers to removing 3 edges in the graphs.

So, 1,1,0,1

0,0,1,0 We should not get any negative value if it's negative, this is not a valid sequence, and Repeat it till we get the '0' sequence.

Option 1: 7, 6, 5, 4, 4, 3, 2, 1

5,4,3,3, 2, 1, 0

3, 2, 2, 1, 0, 0

1,1,0,0,0

0,0,0,0,0

Hence true.

Option 2: 6, 6, 6, 6, 3,3,2, 2

5, 5, 5, 2, 2, 1, 2 (put them in descending order)

5, 5, 5, 2, 2, 2, 1

3, 0, 0, 0, 1 (descending order)

3,1,0,0,0

0,-1,-1,0

Hence False.

Option 3: 7, 6, 6, 4, 4, 3, 2, 2

5,5, 3, 3, 2, 1, 1

4, 2, 2, 1, 0, 1

4, 2, 2, 1, 1, 0 (descending order)

1,1,0,0,0

Hence True.

Option 4: 8, 7, 7, 6, 4, 2, 1, 1

There is a degree 8 but there are only '8' vertices. A vertex cannot have an edge to itself in a simple graph. This is not a valid sequence.

Hence False.

The correct answer is II and IV.

View all questions of this test

View all answers Start learning for free

< Previous Question Next Question >

Explore Courses for GATE exam

Similar GATE Doubts

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?I. 7, 6, 5, 4, 4, 3, 2, 1lI. 6, 6,6, 6, 3, 3, 2, 2III. 7, 6, 6, 4, 4, 3, 2, 2IV. 8, 7, 7, 6, 4,2, 1,1

View answer

Let G be a graph with 10 vertices, and d(v) be the degree of a vertex v. The following conditions are holds for graph G(i) 3 ≤ d(v) ≤5 for each vertex v in G(ii) Not every vertex degree is even(iii) No two odd degree vertices are of the same degree.How many vertices are even degree in G?

View answer

Which of the following statements is/are TRUE for undirected graph?P: Number of odd degree vertices is even.Q: Sum of degrees of all vertices is even.

View answer

Which of the following statements is/are TRUE for undirected graphs?P: Number of odd degree vertices is even.Q: Sum of degrees of all vertices is even.

View answer

In the following question, the first and the last sentence of the passage are in order and numbered 1 and 6. The rest of the passage is split into 4 parts and numbered as 2,3,4, and 5. These 4 parts are not arranged in proper order. Read the sentences and arrange them in a logical sequence to make a passage and choose the correct sequence from the givenoptions.(1) On Diwali, the family rises early in the morning.(2) The whole family, including the young and the old enjoy doing this,(3) Children let off fireworks later in the night with their friends.(4) At sunset, the lamps are lit and the family performs various rituals(5) Father, mother, and children visit relatives and exchange gifts and sweets.(6) Houses look so pretty with lighted lamps all around.

View answer

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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer?

Share with a Friend

Answer this doubt

Question Description
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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer?.

Solutions for 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE. Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.

Here you can find the meaning of 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice 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?a)I and IIb)III and IVc)II and IVd)IV onlyCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice GATE tests.

Explore Courses for GATE exam