Graph Theory - Unlabeled Trees
Hello MHF -
I don't want to see like I'm relying on this forum for HW, so let me qualify this question. If you don't need the qualification, skip on down to the question. I am currently taking Graph Theory and struggling with it. My professor has an annoying (though thoroughly entertaining) tendency to throw interesting theorems at the class. It's been ~10 lectures and we are having our first quiz on Thursday. The following problem is from a 'practice' quiz we took on Monday and, due to the ad hoc nature of the teaching, I don't even know where to begin to start looking for the answer.
Question: Show that the number of non-isomorphic unlabeled trees on n vertices is >= (n^(n-2)) / n! [which converges to e^n]
My attempt to answer: I started by proving that there are n^(n-2) labeled trees for n vertices since the Prufer Code would contain n-2 entries, and each entry could be any of the n vertices; Since each ordered set of numbers gives a distinct labeled tree, n^(n-2) trees.
But how do I get the n! in the denominator?