How to find non-isomorphic trees?
"Draw all non-isomorphic trees with 5 vertices."
I have searched the web and found many examples of the non-isomorphic trees with 5 vertices, but I can't figure out how they have come to their answer. How exactly do you find how many non-isomorphic trees there are and what they look like? Thanks for your time
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ 9 $\begingroup$To give a more helpful answer, it would be good to know why you can't figure out a specific such example drawn from the web. But there are 3 non-isomorphic trees. (I see Brian Scott has just posted an answer which is probably helpful.)
Counting the number of (isomorphism classes of) unlabeled trees with $n$ vertices is a hard problem, and no closed form for this number is known. There is some material on this in Wikipedia.
$\endgroup$
