# Algorithm for Graph generation from the degree sequence?

Given the degree sequence, is there an algorithm that can return a graph G which satisfies the degree sequence?

There can be more than one graph available for a degree sequence. It is enough if the algorithm returns only one of them.

Assume: Undirected graph, no weights, not a multi-graph(only one edge between 2 vertices).

-
Invalidity checks: 1. Sum of degrees is even (undirected) 2. Each degree < n Are there any more invalidity checks i can deduce from the degree sequence input? –  Maverickgugu Jun 25 '11 at 6:18
googling gave me "Havel-Hakimi theorem".. Which i am not sure gives the required output. –  Maverickgugu Jun 25 '11 at 6:21

See this Wikipedia section and the first paper available here; you can also search on 'Hakimi-Havel algorithm'.

-

The degree sequence algorithm that I am speaking of is as follows: (1) Start with the terms of the sequence in decreasing order, (2) Remove the largest term, m, and reduce the next m terms by one, and (3) rearrange the new sequence in decreasing order.

Proving this however is more of a challenge.

-