An ordered $n$-tuple $(d_1, d_2, ..., d_n)$ with $d_1 \ge d_2 \ge \dots \ge d_n$ is called *graphic* if there exists a simple undirected graph with $n$ vertices having degrees $d_1, d_2, ..., d_n$ respectively. Which of the following 6-tuples is NOT graphic?

We can test whether each degree sequence is graphic using the Havel-Hakimi Theorem:

• Option A: $(1, 1, 1, 1, 1, 1)$ Removing $1$: $(1, 1, 1, 1, 0) \to$ removing $1$: $(1, 1, 0, 0) \to$ removing $1$: $(0, 0, 0)$ (all zeros $\implies$ graphic, representing 3 disjoint edges).

• Option B: $(2, 2, 2, 2, 2, 2)$ Removing $2$: $(1, 1, 2, 2, 2) \to$ sort: $(2, 2, 2, 1, 1) \to$ removing $2$: $(1, 1, 1, 1) \to$ sort: $(1, 1, 1, 1) \to$ removing $1$: $(1, 1, 0) \to$ removing $1$: $(0, 0)$ (all zeros $\implies$ graphic, representing a 6-cycle $C_6$).

• Option C: $(3, 3, 3, 1, 0, 0)$ Applying Havel-Hakimi:

  1. Remove the first element $3$ and subtract $1$ from the next $3$ elements:

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

  2. Remove the first element $2$ and subtract $1$ from the next $2$ elements:

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

  Since a negative degree appears, the sequence is NOT graphic.

  *Alternative reasoning:* The two vertices with degree $0$ are isolated, leaving $4$ vertices. For three of these vertices to have degree $3$, each must be connected to all other $3$ vertices. Therefore, all $4$ vertices must have degree at least $3$, which contradicts the presence of a vertex with degree $1$.

• Option D: $(3, 2, 1, 1, 1, 0)$ Removing $3$: $(1, 0, 0, 1, 0) \to$ sort: $(1, 1, 0, 0, 0) \to$ removing $1$: $(0, 0, 0, 0)$ (all zeros $\implies$ graphic).

Therefore, option C is the correct answer.