# Algorithm for generating all unlabeled trees with n nodes?

How can one generate all unlabeled trees with $\le n$ nodes?

That is, generate and store the adjacency matrices of those graphs? (not just count them)

Visualization of all unlabeled trees with $\le6$ nodes:

• There is no polynomial way to generate an algorithm of all unlabeled trees. This number is exponential by the number of nodes $n$ (see [1]). [1]-en.wikipedia.org/wiki/Tree_(graph_theory)#CITEREFOtter1948 Aug 28, 2018 at 15:06
• Aug 23, 2019 at 14:13

Start by considering rooted trees parametrised by vertex count and depth. These have an obvious recursive construction: a rooted tree of one vertex has depth $$0$$; a rooted tree of $$n > 1$$ vertices and depth $$d \ge 1$$ has a root and its children; at least one child has depth $$d-1$$, no child has depth $$\ge d$$, and the total number of vertices of the children is $$n-1$$.
Now, by a theorem of Jordan every tree either has a centre or bicentre. A tree with bicentre is formed by taking two rooted trees of equal depth and adding an edge between their roots. A tree with centre is a rooted tree where at least two children of the root have depth $$d-1$$.