An ordered \(n\)−tuple \((d_1, d_2,\ldots,d_n)\) with \(d_1 \geq d_2 \geq…

Solution: determine which 6-tuple is not graphic using Havel–Hakimi and quick constructive checks.

• (1, 1, 1, 1, 1, 1): Graphic. The degree sum is 6 (even). One realization is three disjoint edges, pairing vertices to give degree 1 to each.

• (2, 2, 2, 2, 2, 2): Graphic. The degree sum is 12 (even). For example, a 6-cycle gives every vertex degree 2, so the sequence is realizable.

• (3, 3, 3, 1, 0, 0): Not graphic. Apply Havel–Hakimi:

  Step 1: (3,3,3,1,0,0) → remove 3 and subtract 1 from the next three degrees → (2,2,0,0,0).

  Step 2: Remove 2 and subtract 1 from the next two degrees. The next two are 2 and 0, so this produces a negative entry (1,−1,...), which is impossible. Therefore the sequence cannot be realized.

  Alternatively, the Erdős–Gallai criterion fails for k=2: the sum of the two largest degrees is 6 while the right-hand bound is 5, so the sequence is not graphic.

• (3, 2, 1, 1, 1, 0): Graphic. Use Havel–Hakimi:

  Step 1: (3,2,1,1,1,0) → remove 3 and subtract 1 from the next three degrees (2,1,1) → (1,0,0,1,0) which sorts to (1,1,0,0,0).

  Step 2: Remove 1 and subtract 1 from the next one degree → all zeros. Since we reach all zeros without contradiction, the sequence is realizable.

Conclusion: Among the four given 6-tuples, only (3, 3, 3, 1, 0, 0) is not graphic.