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?

• The short answer is that you've taken the degree sequence to be an ascending order rather than as a descending order. – hardmath Oct 19 '16 at 0:54
• Yes! thank you. I read that inequality backwards on the wiki page. Should I delete this question? – dfaulken Oct 19 '16 at 0:55
• No, I think it makes a good illustration of the importance of ordering. Why not work out the details and post a self-answer? I would happily upvote a well-written Answer. – hardmath Oct 19 '16 at 0:57
• Will do, thanks. – dfaulken Oct 19 '16 at 2:02

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!

• Nicely done. A similar issue was raised by this recent Question, but it concerns the Havel-Hakimi theorem, so closely related but not an exact duplicate. Your write-up is better, IMHO. – hardmath Oct 19 '16 at 2:15