GATE CS 2010 Q28 — Graphs: Connectivity, Matching, Colouring

For a simple graph with $n$ vertices, the maximum degree of any vertex is at most $n - 1$. Let us analyze the given sequences where $n = 8$:

• Sequence IV: $8, 7, 7, 6, 4, 2, 1, 1$
  Here, $n = 8$, but the maximum degree is $8$. Since a vertex in a simple graph of $8$ vertices can connect to at most $7$ other vertices, a degree of $8$ is impossible. Thus, IV is not graphical.
• Sequence II: $6, 6, 6, 6, 3, 3, 2, 2$
  We apply the Havel-Hakimi theorem to check if it is graphical:
  1. Remove $6$ and subtract $1$ from the next $6$ elements:
     $5, 5, 5, 2, 2, 1, 2 \implies 5, 5, 5, 2, 2, 2, 1$
  2. Remove $5$ and subtract $1$ from the next $5$ elements:
     $4, 4, 1, 1, 1, 1$
  3. Remove $4$ and subtract $1$ from the next $4$ elements:
     $3, 0, 0, 0, 1 \implies 3, 1, 0, 0, 0$
  4. Remove $3$ and subtract $1$ from the next $3$ elements:
     $0, -1, -1, 0$
  Since we obtain negative degrees, II is not graphical.

Applying the same theorem to sequences I and III shows they are graphical. Therefore, sequences II and IV cannot be the degree sequence of any simple graph.