Критерий Эрдеша-Галлаи

Критерий Эрдеша - Галлаи (Erd\"{o}s - Gallai criterion) - критерий графичности числовой последовательности.

Теорема. Правильная [math]\displaystyle{ n }[/math]-последовательность [math]\displaystyle{ d }[/math] является графической тогда и только тогда, когда для каждого [math]\displaystyle{ k }[/math], [math]\displaystyle{ 1 \leq k \leq n-1 }[/math], верно неравенство [math]\displaystyle{ $\sum_{{i=1}^{{k} d_{{i} \leq k(k-1) + \sum_{{i=k+1''^{n} \min\{k, d_{i}\}. }[/math]

Литература

[Лекции]