How many non-isomorphic trees can be made?

943 Views Asked by At

I have to find out how many non-isomorphic binary trees can be made with 5 end vertices, is there some sort of formula to find them all or do I just have to draw them until I can't find anymore?

Edit: the tree must be a full binary tree, so each parent must have either 2 children or no children.

1

There are 1 best solutions below

0
On BEST ANSWER

Since the tree is "full binary" as you describe it, there must be $3$ branch nodes (degree $3$) to split the basic "root plus two leaves" into a tree with $5$ leaves, each branch replacing a leaf to produce $2$ leaves for a net gain of $1$ leaf.

One option is to have one branch node on one side of the root and the other two on the other side; this give one class of isomorphic graphs. With all branches on the same side of the root, they either be arranged linearly (with the furthest branch at distance $3$ from the root), or compactly with two branches at distance $2$ from the root. This gives the remaining two classes of isomorphic graphs.

So $3$ such non-isomorphic graphs can be produced, one from each isomorphic set.