Without using Cayley’s theorem, prove that there are at most $n^{2n−2}$ labelled trees with n vertices.

Question

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 :)

Answer 1

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}$.

Answer 2

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.

Answer 3

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.

Answer 4

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$