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

  • 0
    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?2011-06-25
  • 1
    googling gave me "Havel-Hakimi theorem".. Which i am not sure gives the required output.2011-06-25

2 Answers 2