Number of non-isomorphic trees with given degree sequence

Question

Can we find the total number of pairwise non-isomorphic trees with given degree sequence using the Havel-Hakimi theorem?

Answer 1

The Havel-Hakimi theorem only provides one example graph for a degree sequence if one exists (that is if the sequence is graphical). At each stage, you connect a vertex with maximal remaining degree ($d$) to the next $d$ vertices of maximal remaining degree.

For example, for the sequence [3,3,2,2,1,1] this procedure gives us the two degree three vertices connected together and to the two degree two vertices, while the degree one vertices form another connected component.

Using the indices of the sequence, this is 0->{1,2,3} and then 1->{2,3} and finally 4->{5}. If instead we take 0->{2,3,4} and then 1->{2,3,5} we get a different graph.

Unfortunately different choices of connections at each step can lead to isomorphic graphs, so it's not as simple as just running through all possibilities.