Is there any algorithm to build or count the labeled non-isomorphic trees on $n$ vertices ?
[Math] Number of labeled non-isomorphic trees on $n$ vertices
graph theorytrees
Related Solutions
You're essentially asking for the number of non-isomorphic trees on $4$ vertices. Here they are:
We can verify that we have not omitted any non-isomorphic trees as follows.
The total number of labelled trees on $n$ vertices is $n^{n-2}$, called Cayley's Formula. When $n=4$, there are $4^2=16$ labelled trees.
The number of labelled graphs isomorphic to a graph $G$ is given by $$\frac{n!}{|\mathrm{Aut}(G)|}$$ where $n$ is the number of vertices of the graph, and $\mathrm{Aut}(G)$ is the automorphism group of the graph. This is a consequence of the Orbit-Stabiliser Theorem. In the above two cases, the automorphism groups have size $6$ (and is isomorphic to $S_3$) and $2$, respectively.
So the $16$ labelled $4$-vertex trees partition into $24/6=4$ trees isomorphic to the tree on the left and $24/2=12$ trees isomorphic to the tree on the right. Since $16=4+12$, we have accounted for all isomorphism classes of trees.
(Note: more than half of the labelled $4$-vertex trees are isomorphic to the graph on the right.)
One systematic approach is to go by the maximum degree of a vertex. Clearly the maximum degree of a vertex in a tree with $5$ vertices must be $2,3$, or $4$. If there is a vertex of degree $4$, the tree must be this one:
*
|
*--*--*
|
*
At the other extreme, if the maximum degree of any vertex is $2$, the tree must be the chain of $5$ vertices:
*--*--*--*--*
That leaves the case in which there is a vertex of degree $3$. In this case the fifth vertex must be attached to one of the leaves of this tree:
*
\
*--*
/
*
No matter to which leaf you attach it, you get a tree isomorphic to this one:
*
\
*--*--*
/
*
Thus, there are just three non-isomorphic trees with $5$ vertices.
Related Question
- [Math] Drawing all non-isomorphic trees with $n = 5$ vertices.
- How to show that there will be at most $4^{n+1}$ pairwise non-isomorphic trees on $n+1$ vertices
- List of non-isomorphic trees on (up to $21$ vertices)
- Number of labeled trees with given subgraph using prufer code.
- Number of undirected trees with unlabled vertices and labeled edges
Best Answer
From your comment, it sounds like you consider two labeled trees isomorphic if they have the same (labeled) degree sequence. Thus to count the number of non-isomorphic labeled trees we'd want the number of labeled degree sequences of trees on $n$ vertices, which is ${2n-3 \choose n-1}$.
Why is it ${2n-3 \choose n-1}$? Well, a degree sequence corresponds to a tree if and only if every degree is at least 1 and the degree sum is 2n-2. Thus, we need the number of n-tuples of positive integers that sum to 2n-2, which is ${2n-3 \choose n-1}$.