Какие основные проблемы возникают при построении графов с определенными степенями вершин?

Некоторые основные проблемы, которые возникают при построении графов с определёнными степенями вершин:

• Проблема последовательности степеней. ru.wikipedia.org Заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел. ru.wikipedia.org При этом любая последовательность с нечётной суммой не может быть последовательностью степеней графа. ru.wikipedia.org
• Сложности с реализацией простого графа с заданной последовательностью. ru.wikipedia.org Согласно теореме Эрдёша — Галлаи, невозрастающая последовательность может быть последовательностью простого графа только если её сумма чётна и выполняется определённое неравенство. ru.wikipedia.org
• Отсутствие возможностей для однозначной идентификации структуры графа. cyberleninka.ru Для однородных графов такая ситуация возникает уже, например, при приближении значений n к 15–20 вершинам. cyberleninka.ru Для неоднородных графов, содержащих десятки и сотни вершин, даже применение алгоритмов, учитывающих специфику отдельных графов, объёмы вычислений часто становятся нереалистичными. cyberleninka.ru