<s>[INST] Confused about Erdos-Gallai theorem 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?
 [/INST] 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!
</s>