Confused about Erdos-Gallai theorem

Question

Consider the sorted degree sequence $1,3,3,3$.

Erdos-Gallai states that for $k$ in $1 \leq k \leq n$:

$$\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{j=k+1}^n min(d_j,k)$$.

And that $\Sigma d_i$ must be even, which it is.

$k=1$ gives the inequality $1 \leq 1(0) + (1 + 1 + 1)$, or $1 \leq 3$, which passes.

$k=2$ gives the inequality $1 + 3 \leq 2(1) + (2 + 2)$, or $4 \leq 6$, which passes.

$k=3$ gives the inequality $1 + 3 + 3 \leq 3(2) + (3)$, or $7 \leq 9$, which passes.

$k=4$ gives the inequality $1 + 3 + 3 + 3 \leq 4(3)$, or $10 \leq 12$, which passes.

But it's easy to see that the degree sequence $1, 3, 3, 3$ is agraphical. What am I missing here?

Answer 1

As hardmath commented, my ordering was backwards. Erdos-Gallai states that the degree sequence must be ordered largest degree first; that is, the sequence must be $3,3,3,1$.

So we have:

$k=1$ gives $3 \leq 1(0) + (1 + 1 + 1)$, or $3 \leq 4$, which passes.

$k=2$ gives $3 + 3 \leq 2(1) + (2 + 1)$, or $6 \leq 5$, which fails.

Then we're done, but for good measure:

$k=3$ gives $3 + 3 + 3 \leq 3(2) + 1$, or $9 \leq 7$, which fails.

$k=4$ gives $3 + 3 + 3 + 1 \leq 4(3)$, or $10 \leq 12$, which passes.

Thanks hardmath!