Question 62

According to the Havel-Hakimi Theorem, a non-increasing sequence $d_1, d_2, \dots, d_n$ is graphic if and only if the sequence obtained by deleting $d_1$ and subtracting 1 from each of the next $d_1$ terms is graphic.

Let us test the 6-tuples:

• Option (A) $(1, 1, 1, 1, 1, 1)$:
  Three disjoint edges ($3 K_2$). Graphic.

• Option (B) $(2, 2, 2, 2, 2, 2)$:
  A 6-cycle ($C_6$). Graphic.

• Option (C) $(3, 3, 3, 1, 0, 0)$:
  Remove $d_1 = 3$ and subtract 1 from the next 3 terms:

  $$(3 - 1, 3 - 1, 1 - 1, 0, 0) = (2, 2, 0, 0, 0)$$

  Sort: $(2, 2, 0, 0, 0)$.
  Now remove $d_1 = 2$ and subtract 1 from the next 2 terms:

  $$(2 - 1, 0 - 1, 0, 0) = (1, -1, 0, 0)$$

  This contains a negative degree ($-1$), which is impossible in any graph.
  Therefore, $(3, 3, 3, 1, 0, 0)$ is NOT graphic.

• Option (D) $(3, 2, 1, 1, 1, 0)$:
  Remove 3 and subtract 1 from next 3 terms:

  $$(2 - 1, 1 - 1, 1 - 1, 1, 0) = (1, 0, 0, 1, 0)$$

  Sort: $(1, 1, 0, 0, 0)$.
  Remove 1 and subtract 1 from next term:
  $(1 - 1, 0, 0, 0) = (0, 0, 0, 0)$, which is graphic.
  Thus (D) is graphic.

Hence, $(3, 3, 3, 1, 0, 0)$ is NOT graphic.