Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.)
