Можно рассмотреть задачу в более общем виде: построение графа с заданной степенной послодовательностью. Решается она с помощью алгоритма, называемого иногда L-процедурой. Так вот в этой L-процедуре на каждом шаге есть определенная свобода выбора, поэтому выбор можно делать случайный.

Как работает L-процедура. Построим пустой граф из n вершин, рядом с каждой вершиной v напишем число d(v) -- требуемую степень. Выберем произвольную вершину v с d(v) > 0 (если таковых нет, то работа завершена). Рассмотрим множество A, состоящее из d(v) вершин, отличных от v и имеющих наибольшие значения d. Соединим v с вершинами из A;
скорректируем требуемые степени (уменьшим d(v) и d(x), x \in A) на единицу. Перейдем к следующему шагу.

Известно, что если реализация последовательности вообще существует, то L-процедура ее найдет (при любом выборе вершин v) -- это т.н. теорема Гавела-Хакими. Реализация алгоритма будет достаточно быстрой, если использовать для выбора A приоритетную очередь. Тогда получается сложность O(E \log V).