7
$\begingroup$

The conditions for a sequence to be the degree sequence of a simple graph are given by the Erdos-Gallai theorem in addition to the handshaking lemma. Is there an example of a degree sequence where the handshaking lemma is satisfied, but the Erdos-Gallai theorem is not satisfied and thus, the sequence is not graphic (or vice versa).

Or, does satisfying one of these conditions ensure the other is always satisfied?

$\endgroup$
1
  • 1
    $\begingroup$ There are examples where the lemma is satisfied, but the inequality is not, and there are examples where the inequality is satisfied, but the lemma is not. It would be instructive for you to come up with such examples – it's not that hard! $\endgroup$ Jan 6 at 2:47
5
$\begingroup$

Let $n=3$ and $d_1=d_2=d_3=1$. Then

$$\begin{align*} &\sum_{i=1}^1d_i=1\le 2=1\cdot0+\sum_{i=2}^3\min\{d_i,1\}\,,\\ &\sum_{i=1}^2d_i=2\le 3=2\cdot1+\sum_{i=3}^3\min\{d_i,1\}\,,\text{ and}\\ &\sum_{i=1}^3d_i=3\le 6=3\cdot2+\sum_{i=4}^3\min\{d_i,1\}\,. \end{align*}$$

Thus, the sum of the degrees is odd, but the sequence satisfies the inequality in the Erdős-Gallai theorem.

Obviously one cannot satisfy the full hypotheses of the theorem without also satisfying the handshaking requirement that the sum of the degrees be even, since those hypotheses include the requirement that the degrees be even. However, that requirement is made solely to ensure that the handshaking lemma is satisfied. The meat of the theorem is the inequality, and this example shows that it is possible for a sequence to satisfy that without satisfying the handshaking lemma. (Examples that satisfy the handshaking lemma but not the inequalities are not hard to find.)

$\endgroup$
4
  • 2
    $\begingroup$ The Erdős-Gallai theorem states that the sum of the degrees must be even. The inequalities are satisfied but the theorem is not. Could you clarify what this example is showing? $\endgroup$ Jan 6 at 10:45
  • 1
    $\begingroup$ @DavidScholz: I thought it obvious. The OP showed interest in both possibilities (‘or vice versa’). It’s clearly impossible for the hypotheses of the Erdős-Gallai theorem to be satisfied and the handshaking lemma to fail, for the reason that you give, but the real meat of the E-G theorem is the inequality, and that can hold even if the sum of the degrees is not even. That’s as close to ‘vice versa’ as you can get. As I say, I thought this fairly obvious, but I’ve added further explanation to the answer. $\endgroup$ Jan 6 at 19:03
  • 1
    $\begingroup$ Thank you! To summarize: Sum of degrees is uneven and the EG equalities could still hold, even if the theorem in its whole does fail. The other case, provided by Mike, shows the other way around: sum of degrees even and EG not satisfied. I think that this discussion was useful, thanks for participating. $\endgroup$ Jan 7 at 8:21
  • 1
    $\begingroup$ @DavidScholz: Yes, exactly. You’re welcome! $\endgroup$ Jan 7 at 8:22
2
$\begingroup$

The simplest example would be $$ (2,0,0) $$ The handshaking lemma is satisfied, but the Erdős–Gallai inequalities are not, as $2\not\le 1\cdot (1-1)+0+0$.

$\endgroup$
0

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.