[Math] What are the 9 non-isomorphic rooted trees with 5 vertices

graph theorygraph-isomorphismtrees

I'm wondering what the non-isomorphic rooted trees with 5 vertices look like. According to the textbook I'm reading, there are 9 of them but I don't know what they look like or how to draw them or if I'm just misunderstanding the question.

Thanks for you help!

Best Answer

These are the 9 non-isomorphic rooted trees with 5 vertices.

Related Solutions

Discrete Mathematics – How to Find Non-Isomorphic Trees

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.

[Math] Determine number of directed trees and rooted trees obtainable

I would attack it this way. I'd use the Matrix-Tree Theorem to obtain the number of unrooted spanning trees. You can then apply $n$ orientations to each tree. So by rule of product, multiply your result from the Matrix-Tree Theorem by $n$.

Best Answer

Related Solutions

Discrete Mathematics – How to Find Non-Isomorphic Trees

[Math] Determine number of directed trees and rooted trees obtainable

Related Question