1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ You can have infinitely many non isomorphic versions. First make a single binary tree with five end vertices and make each branch as long as you like by adding a path of length $n$. Unless you want trees on a fixed number of vertices, in which case you should say so. $\endgroup$ – RKD Oct 21 '17 at 18:49
  • $\begingroup$ I forgot to mention that the tree must be a full binary tree, so each parent must have either 2 children or no children. $\endgroup$ – animorphlover3 Oct 21 '17 at 18:58
  • 2
    $\begingroup$ So edit your question accordingly $\endgroup$ – RKD Oct 21 '17 at 19:04
1
$\begingroup$

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.

Improve this answer
$\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.