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


Solution 1:

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.

Solution 2:

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.