Labeled tree generation given degree sequence I'm looking for some algorithm implementations for generating all labelled trees having the degree sequence as an input. I have found the Nakano's article: http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1644-06.pdf, however the implementation is nowhere to be found and implementing it on my own just from the text would be at least difficult. Are there any ready implementations? I use Sagemath on a daily basis, however I believe its implementation in 'graphs' is based on generating all graphs and then checking whether the degree sequence fits, which is quite unaccaptable. 
If anyone were to recommend any implementation of the unlabelled trees with given degree sequence that would be highly appreciated as well, however it is not the main question.
 A: You can go in three steps:


*

*Find all permutations of the multiset $d_1, d_2, d_3, \dots, d_n$. (SageMath has a deprecated permutations_iterator() for doing this, I'm not sure if there's a non-deprecated alternative.)

*For each such permutation $(D_1, D_2, \dots, D_n)$, assume that $D_i$ will be the degree of vertex labeled $i$. We will generate all such trees by first generating their Prüfer codes. To do this, generate the length $n-2$ sequence $$s = (\underbrace{1,1,\dots,1}_{D_1-1}, \underbrace{2,2,\dots,2}_{D_2-1}, \dots, \underbrace{n,n,\dots,n}_{D_n-1}).$$ It's a property of Prüfer codes that a tree where vertex $i$ has degree $D_i$ has a Prüfer code where label $i$ appears $D_i-1$ times.

*Once again, find all the permutations of $s$. For each one, generate the tree with that Prüfer code. SageMath doesn't seem to have a command for this, though I'm sure it will eventually, but here are some implementations of this procedure in several common languages.


Here is my Mathematica code for the above; to do the Prüfer code step, I use IGraph/M, a Mathematica interface to igraph.
<< IGraphM`
listTrees[degrees_] :=
  Module[{n = Length[degrees], code, results = {}},
    Do[
      code = Flatten@Table[i, {i, 1, n}, {j, 1, perm[[i]] - 1}];
      results = Join[results, IGFromPrufer /@ Permutations[code]];
    ,{perm, Permutations[degrees]}];
    Return[results]
  ];

