Number of isomorphism classes of a tree on n vertices

Question

I'm currently trying to solve this problem:

"Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n-2}}{n!}$."

I'm pretty stumped to be honest. I know of Cayley's formula; there are $n^{n-2}$ trees on n labelled vertices, so I'm guessing that this may come in handy.

One idea I had was to find the most number of isomorphism classes. This, I believe, should be n-2, for $n \geq 2$, and 1, for $n=0, 1$. But then I don't particularly think this would be of any use or would lead to a very forced way to prove it.

Any hints / ideas? Thanks!

Answer 1

$n^{n-2}$ is smaller than or equal to the number of isomorphism classes times $n!$ because all trees in an isomorphism class are given by a permutation of the vertices, so your bound is a lower bound on the number of isomorphism classes.

Answer 2

Labelled graphs are easier to deal with, and especially to count, than isomorphism classes because different isomorphism classes behave more differently to each other than different labelled graphs do. In particular, it varies a lot how many different labelled graph a given isomorphism class will produce: the path produces n!/2 whereas the star produces n. (I believe these are the respective maxima and minima for n>=3 but i could be wrong.)

We know how many labelled graphs the isomorphism classes produce overall, so this is going to be our bound. We cannot produce more, or fewer, labelled graphs than these. We want to find the minimum conceivable number of isomorphism classes, so we want to stick to the case where each one produces as many labelled graphs as possible. Well, that’s not too hard to (over?) estimate: if you draw a graph from each isomorphism class out, you can produce every labelling possible by making a different choice of how to assign the numbers 1 to n to each of the n dots in your drawing. This is a bijection between two sets with n elements, so there’s n! ways to do this.

Putting this all together, we see that #LG = n^{n-2} =< #IC x n! and the result follows