Does Cayley's formula count isomorphic trees?

205 Views Asked by At

Cayley's formula tells us that on $n$ vertices, there exist $n^{n-2}$ trees.

Now I am wondering if this formula considers each set of isomorphic trees as 1 or if it counts every one of them.

1

There are 1 best solutions below

0
On BEST ANSWER

First, note that there is no known closed form expression for the number of unlabeled trees up to isomorphism.

Cayley's Formula on the other hand gives us the number of labeled trees up to isomorphism. Note that in labeled case, for example the following graphs are not considered isomorphic although if they were unlabeled, we would consider them isomorphic. But if you look at their labeling carefully, they are all different.

enter image description here