The GATE Grind

GATE 2014 CS (CS1) – Question 62

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

A nonincreasing n-tuple is graphic if a simple undirected n-vertex graph has those degrees. Which tuple is NOT graphic?

  1. (1,1,1,1,1,1)
  2. (2,2,2,2,2,2)
  3. (3,3,3,1,0,0)
  4. (3,2,1,1,1,0)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) (3,3,3,1,0,0)

Explanation

Sequence C has three vertices of degree3, one of degree1 and two isolated vertices. On the four nonisolated vertices, each degree3vertex must connect to every other nonisolated vertex. The purported degree1vertex would then have at least three neighbours, a contradiction. Thus **C** is not graphic.