GATE 2010 CS (CS1) – Question 38

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

Which sequences cannot be degree sequences of simple graphs?

I: 7,6,5,4,4,3,2,1
II: 6,6,6,6,3,3,2,2
III: 7,6,6,4,4,3,2,2
IV: 8,7,7,6,4,2,1,1

I and II
III and IV
IV only
II and IV

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) II and IV

Explanation

IV is impossible because a simple graph on eight vertices has maximum degree seven. For II, the four largest degrees sum to twenty-four, whereas their maximum possible contribution is 4×3+3+3+2+2=22, violating the Erdős–Gallai inequality. Havel–Hakimi reduction verifies I and III. Therefore II and IV, D, are impossible.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2015 CS (CS2) Q61 – A self-complementary graph is isomorphic to its complement. What must its vertex count n…
GATE 2015 CS (CS2) Q62 – A bridge is an edge whose removal disconnects a connected graph. Which is true?
GATE 2026 CS (CS1) Q55 – An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists…
GATE 2026 CS (CS2) Q36 – Consider a complete graph K n with n>4 vertices. Each spanning tree of K n is represented…
GATE 2024 CS (CS1) Q34 – The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is
GATE 2024 CS (CS1) Q51 – The chromatic number of a graph is the minimum number of colours used in a proper…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →