1
$\begingroup$

I followed the instructions in this question to create the trees for n = 1, n = 2, n = 3, n = 4, and n = 5. Note that I created rooted trees instead of free trees because it was easier. You can get the free tree versions by just messing with the branch arrangements. The problem is taken from my book, which asks me to draw all non-isomorphic trees with $5$ vertices. Here's what I did:

enter image description here

The book has the following answer for $n = 5$. Two of my trees (the two on the left labeled $n = 5$) match the ones given by the book, but the third tree I drew does not match the tree they have where one node has 4 branches.

enter image description here

What exactly did I do wrong?

$\endgroup$
4
$\begingroup$

Your last two five vertex trees are isomorphic. Each has one vertex with degree $3$ and that vertex has chains of $1,1,2$ leaving it. The three leaves of the first $n=4$ graph are equivalent and you added a leaf to two of them. You need to add a leaf to the degree $3$ vertex to get the last $n=5$ tree.

$\endgroup$
  • $\begingroup$ Oh, brilliant, I see that now! Thank you :) $\endgroup$ – AleksandrH Jul 29 '17 at 20:53

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.