Как вычислить число возможных графов по последовательности их степеней?

Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов. 1

Есть некоторые методы, которые могут помочь в решении этой задачи:

• Теорема Эрдёша — Галлаи. 1 Утверждает, что невозрастающая последовательность может быть последовательностью простого графа, только если её сумма чётна и выполняется определённое неравенство. 1
• Критерий Гавела — Хакими. 1 Позволяет построить полиномиальный алгоритм нахождения простого графа с заданной реализуемой последовательностью. 1
• Алгоритм построения мультиграфа. 1 Если последовательность имеет чётную сумму, можно построить мультиграф: объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам добавить петли. 1

Также известно, что чтобы подсчитать число рёбер графа, нужно просуммировать степени вершин и полученный результат разделить на два. 4 При этом сумма степеней всех вершин графа должна быть чётной (иначе её нельзя было бы разделить на два нацело). 4