Теорема Эрдёша-Галлаи — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа. 23

Использование теоремы Эрдёша-Галлаи в анализе последовательностей степеней графов заключается в следующем:

1. Определение правильной последовательности. 2 Это последовательность натуральных чисел длины n, удовлетворяющая условиям: n−1 ≥ d1 ≥ d2 ≥ … ≥ dn, сумма чисел чётная. 34
2. Определение графической последовательности. 2 Это последовательность целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней. 2
3. Проверка неравенства Эрдёша-Галлаи. 2 Для каждого члена уже отсортированного массива проверяется неравенство. 2 При его невыполнении необходимая разница (для того, чтобы неравенство стало верным) прибавляется к правой части, либо отнимается от левой. 2 При этом так, чтобы последовательность оставалась невозрастающей. 2
4. Получение верного массива. 2 На выходе получается верный массив степеней вершин. 2
5. Заполнение графа дугами. 2 Заполнение идёт по схеме: наибольшее — наименьшему, то есть нужно идти с начала массива и каждую вершину связывать с вершинами с наименьшей степенью (если они уже не соединены). 2

Построить граф по графической последовательности можно полиномиальным алгоритмом, который строится на основании критерия Гавела — Хакими. 34