Задача о реализации графа

Задача о реализации графа — задача разрешимости в теории графов. Задана конечная последовательность $(d_1,\dots ,d_n)$ натуральных чисел, задача спрашивает, существует ли такой простой граф, в котором $(d_1,\dots ,d_n)$ — последовательность степеней вершин этого графа.

Решения

Задача может быть решена за полиномиальное время. Одним из примеров таких решений является алгоритм Гавела — Хакими, в основе которого лежит рекурсия. Задачу также можно решить путем проверки справедливости $n$ неравенств, используя теорему Эрдёша — Галлаи.