Let G be a simple undirected graph. If it has at most $4$ edges, there is only one graph for any degree-sequence, but for $n = 5$, the situation changes. There are $34$ different (non-isomorphic) graphs, but only $31$ degree-sequences. For $n\ge 6$ the discrepance becomes already quite large.
According to wikipedia, no efficient algorithm is known to determine whether two given graphs are isomorphic. But I wonder if the enumeration and the calculation of the number of different graphs is easier :
- How many different graphs do exist for a given degree-sequence ?
- What is the best method to enumerate the different graphs ?