# What is the maximal number of spanning trees that can be constructed in K9?

I'm a bit confused as how I should do this. Two spanning trees I know can be constructed from K9 are using DFS and BFS. But I'm not sure how I should be creating the others? Should I just draw the graph and start taking out cycles until I have trees? Also I'm a bit confused as to the definition of different spanning trees (without common edges)... does that mean that just having one differing edge will suffice? I'd appreciate any help. Thanks!

Edit: I'm curious in finding the number of nonisomorphic trees.

• Assuming $K_9$ is the complete graph on $9$ vertices, you may have a look at en.wikipedia.org/wiki/Cayley%27s_formula – Jack D'Aurizio Mar 26 '18 at 16:26
• @JackD'Aurizio Yes, I meant the complete graph on 9 vertices. Thank you! I should've specified this in the post, but I was wondering how I would do this for non-isometric trees? It seems as if Cayley's Formula counts the different number of orderings for isometric trees as well. – jack klompus Mar 26 '18 at 17:07
• Do you mean non-isomorphic trees? – Misha Lavrov Mar 26 '18 at 18:37
• @MishaLavrov It seems like I'm dyslexic. Thank you, I meant non-isomorphic. – jack klompus Mar 28 '18 at 1:15

## 1 Answer

Usually, when people talk about counting spanning trees in a graph, they do mean to count labeled spanning trees: isomorphic trees that use different vertices get counted separately. And there, the answer is for $K_9$ is just $9^7$ by Cayley's theorem.

If we want to count unlabeled spanning trees (that is, isomorphism classes of spanning trees), then the problem becomes much harder. This is sequence A000055 in the OEIS, and so we know that the answer for $K_9$ is $47$. But there's no exact formula.

Here are some easy estimates for a lower bound and an upper bound.

1. We can just divide the labeled answer $n^{n-2}$ by $n!$, the maximum number of isomorphic copies of the same tree. This is a lower bound, since for some isomorphism classes, there are many fewer copies than that. But it tells us that the answer is at least $$\frac{n^{n-2}}{n!} \sim \frac{n^{n-2}}{\sqrt{2\pi n}(\frac ne)^n} = \frac1{\sqrt{2\pi} n^{5/2}} \cdot e^n.$$ For $n=9$, we get $\left\lceil\frac{9^7}{9!}\right\rceil =14$ as a lower bound this way.
2. For every tree, we can (1) pick a root and (2) for every node, pick an arbitrary order to its children, getting an ordered tree. The ordered trees on $n$ vertices are counted by the Catalan numbers $$C_n = \frac1{n+1} \binom{2n}{n} \sim \frac{1}{\sqrt \pi n^{3/2}} 4^n.$$ For $n=9$, we get an upper bound of $4862$ in this way.

These bounds might not be very close together, but at least they tell us that the number of unlabeled trees grows exponentially, and the base of the exponent is between $e$ and $4$. A theorem of George Pólya says that actually the exponent is $b \approx 2.9557$, but this is much harder to prove.