# Number of undirected trees

Given n numbered vertices I want to know the number of different trees that can be created with them. I know that cayley's theorem says it's $n^{n-2}$, but why can't it also be: $\binom{\binom{n}{2}}{n-1}$

Since $\binom{n}{2}$ is the number of edges out of which I choose $n-1$ (which makes it a graph with $n$ nodes and $n-1$ edges which is a tree.

• That second term is number of ways to select $n-1$ edges from all edges, but not every such graph would be a tree – Adam Jun 28 '13 at 11:02
• You're right. How could I have missed that.... Thanks :) – Shookie Jun 28 '13 at 11:04

A graph with $n$ nodes and $n-1$ edges is a tree iff it is connected.

So, you are also counting a lot of unconnected graphs. For instance, if $n=4$, take a triangle and an isolated vertex. Then the number of edges is $3$, but the graph is not a tree.

However, you gave a nice combinatorical proof, that $$n^{n-2}<\binom{\binom{n}{2}}{n-1}$$ for $n>3$.

Some sets of $n-1$ edges don’t make trees. Consider building a graph by choosing $3$ of the $\binom42=6$ possible edges among $4$ vertices: $4$ of the resulting graphs consist of a triangle and an isolated vertex, and those graphs are not trees, or even forests.

(By the way, there’s a correct (albeit slightly snarky and not terribly informative) answer to the question ‘why can’t it also be’: because in general

$$n^{n-2}\ne\binom{\binom{n}2}{n-1}\;,$$

so it can’t be both! You really want instead, not also.)