5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The short answer is that you've taken the degree sequence to be an ascending order rather than as a descending order. $\endgroup$ – hardmath Oct 19 '16 at 0:54
  • $\begingroup$ Yes! thank you. I read that inequality backwards on the wiki page. Should I delete this question? $\endgroup$ – dfaulken Oct 19 '16 at 0:55
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Oct 19 '16 at 0:57
  • $\begingroup$ Will do, thanks. $\endgroup$ – dfaulken Oct 19 '16 at 2:02
5
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Oct 19 '16 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.