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

Question

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.

Answer 1

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.