Erdos--Gallai criterion

Erd\"{o}s--Gallai criterion --- критерий Эрдёша--Галлаи.

A sequence of integers [math]\displaystyle{ d_{1}, \ldots, d_{n} }[/math] with [math]\displaystyle{ n - 1 \geq d_{1} \geq \ldots \geq d_{n} }[/math] is a graphic sequence of numbers iff

(1) [math]\displaystyle{ \sum_{i=1}^{n} d_{i} }[/math] is even, and

(2)[math]\displaystyle{ \sum_{i=1}^{r} d_{i} \geq r(r-1) + \sum_{i=r+1}^{n} \min\{r,d_{i}\} }[/math] for [math]\displaystyle{ r =2, \ldots, n-1 }[/math].

(the [math]\displaystyle{ r }[/math]-th Erd\"{o}s-Gallai inequality).