Confundido acerca de Erdos-Gallai teorema de

Question

Considerar la ordenada grado de secuencia $1,3,3,3$.

Erdos-Gallai establece que para$k$$1 \leq k \leq n$:

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

Y que $\Sigma d_i$ debe ser, incluso, que lo es.

$k=1$ da la desigualdad de $1 \leq 1(0) + (1 + 1 + 1)$ o $1 \leq 3$, que pasa.

$k=2$ da la desigualdad de $1 + 3 \leq 2(1) + (2 + 2)$ o $4 \leq 6$, que pasa.

$k=3$ da la desigualdad de $1 + 3 + 3 \leq 3(2) + (3)$ o $7 \leq 9$, que pasa.

$k=4$ da la desigualdad de $1 + 3 + 3 + 3 \leq 4(3)$ o $10 \leq 12$, que pasa.

Pero es fácil ver que el grado de secuencia $1, 3, 3, 3$ es agraphical. Lo que me estoy perdiendo aquí?

Answer 1

Como hardmath comentado, mi pedido era al revés. Erdos-Gallai afirma que el grado de la secuencia deben ser ordenados de mayor grado primero; es decir, la secuencia debe ser $3,3,3,1$.

Por lo tanto tenemos:

$k=1$ da $3 \leq 1(0) + (1 + 1 + 1)$ o $3 \leq 4$, que pasa.

$k=2$ da $3 + 3 \leq 2(1) + (2 + 1)$ o $6 \leq 5$, lo que falla.

A continuación, hemos terminado, pero por una buena medida de frente:

$k=3$ da $3 + 3 + 3 \leq 3(2) + 1$ o $9 \leq 7$, lo que falla.

$k=4$ da $3 + 3 + 3 + 1 \leq 4(3)$ o $10 \leq 12$, que pasa.

Gracias hardmath!