One thing to add to the algorithm, which I forgot, is a quick check to ensure the sum of the degrees is even. Silly me.

# my $g = Graph->new_from_degree_sequence(\@degrees, \@vertices);
# my ($g, $iters) = Graph->new_from_degree_sequence(\@deg, \@vert);
# the vertices are optional

sub new_from_degree_sequence {
  my ($class, $deg, $vert) = @_;
  my $sorted = 1;

  # determine the sortedness of the degree sequence,
  # and do a checksum while we're at it
  {
    my $odd = $deg->[0] & 1;

    for (1 .. $#$deg) {
      $sorted &&= 0 if $deg->[$_] > $deg->[$_-1];
      $odd = !$odd if $deg->[$_] & 1;
    }

    $@ = "sum of degrees (@$deg) is odd", return if $odd;
  }

  # determine if the vertices are references,
  # and install default vertex names if needed
  my $ref = 0;
  if ($vert) { for (@$vert) { $ref = 1, last if ref } }
  else { $vert = [map chr(64 + $_), 1 .. @$deg] }

  # create the graph, and store the vertex-degree info
  my $graph = Graph::Undirected->new(vertices => $vert, refvertexed =>
+ $ref);
  my @v = map [$vert->[$_], $deg->[$_]], 0 .. $#$vert;

  my $iter = 0;

  # continue while there are still vertices left to connect
  # only sort the remaining vertices if they weren't already sorted
  while (@v and ($sorted ||= (@v = sort { $b->[1] <=> $a->[1] } @v))) 
+{
    # if we don't have enough vertices, stop
    $@ = "impossible degree sequence (@$deg)", return if @v < $v[0][1]
+;

    ++$iter;

    # connect the vertex with the highest degree (N)
    # to N other vertices with the highest degrees
    for (my $i = $v[0][1]; $i >= 1; --$i) {
      $graph->add_edge($v[0][0], $v[$i][0]);
      --$v[$i][1] or splice @v, $i, 1;
    }

    shift @v;

    # see if the remaining vertices need sorting
    for (1 .. $#v) { $sorted = 0, last if $v[$_][1] > $v[$_-1][1] }
  }

  return wantarray ? ($graph, $iter) : $graph;
}
[download]