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

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

Решения

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