3
$\begingroup$

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).

  • 1
    googling gave me "Havel-Hakimi theorem".. Which i am not sure gives the required output.2011-06-25

2 Answers 2

2

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

0

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.