3
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.