Without using Cayley’s theorem, prove that there are at most $n^{2n−2}$ labelled trees with n vertices. I am studying for a test I have and I found a past problem which I have no idea how to go about doing..
My thoughts are.  I know not to use Cayley's theorem but it says that there are $n^{n-2}$ labelled trees on n vertices.
Thanks :)
 A: A tree has (exactly) $n-1$ edges, each of which involve 2 (distinct) vertices.
Now, consider the number of graphs on $n$ vertices with $n-1$ edges, where for simplicity of counting we allow multiple edges between vertices. There are $ { n \choose 2 } ^{n-1} $ such graphs, and these is clearly less than $n^{2n-2}$.
A: The statement you are trying to prove uses nothing more than the fact that a tree has $n-1$ edges. To satisfy @ijkilchenko: this follows from the fact that a tree which has any edge at all, must have a vertex of degree 1 (if not, we can follow a path through vertices until it intersects itself, at which point we have a cycle). Collapsing the edge to the vertex of degree 1 we have an object with one fewer vertex and one fewer edge, which is still a tree (collapsing the edge does not create cycles). By induction, we can collapse edges until we get a graph with no edges. Since collapsing an edge does not increase the number of connected components, we must have a single vertex, and no edges, so $|v-e|$ (which is constant throughout the collapsing process) is $1,$ which is what we claimed.
A: You can identify a labeled tree, with an arbitrary labeling $e_1,..,e_{n-1}$ of the edges, with a function 
$$f: \{1,2,.., n-1\} \to \{ 1, 2, ...,n \} \times \{1,2,...,n\} $$
via 
$$f(e_i)=(j,k)$$
As the number of such functions is $(n^2)^{n-1}$ we are done.
A: So the number of ways to label a tree is $(\frac{n(n-1)}{2})^{n-1}$  
We can see that :
$(\frac{n(n-1)}{2})^{n-1}  < (\frac{n*n}{2})^{n-1} < (n*n)^{n-1}$
$(n*n)^{n-1} = n^{2(n-1)}$
$\blacksquare$
