Who are you, Mister Graph?

Если суммарная степень нечетная, либо степень какой-то вершины превышает N-1 - искомого графа не существует. Иначе возьмем вершину максимальной степени, добавим от нее ребра к К вершинам с наибольшими степенями, где К - степень данной вершины, уменьшив при этом степени всех вершин к которым мы провели ребра на 1. Далее будем повторять то же самое. Таким образом мы построим требуемый граф. Реализовать это можно за O(NlogN).

Докажем что алгоритм верен. Если есть граф из 2 вершин, то очевидно таким образом мы построим его. Пусть теперь есть граф из  N вершин ненулевой степени, причем суммарная их степень четная (1 условие) и максимальная степень не превышает N-1 (2 условие) и известно что для любого графа из N-1 вершины, для которого выполняются 2 условия, указанными операциями можно построить его. После выбора вершины степени К и выполнения указанной операции суммарная степень уменьшится на 2К, поэтому первое условие не нарушится. Если максимальная степень вершины меньше N-1, тогда после выполнения операции второе условие тоже будет выполняться. Если она равна N-1, то после операции степени всех остальных вершин уменьшатся на 1, поэтому никакая степень не будет превышать N-2.