Difference between tree, rooted tree and plane rooted tree?

Question

I am trying to solve a set of problems that require me to find all trees/rooted trees/plane rooted trees with 4 vertices (up to isomorphism). I have a general idea of how to find all trees with 4 vertices, looking by their degrees, but I do not understand what changes must I make in my search for these trees in the case of rooted trees or plane rooted trees. I know what these terms mean, but I do not understand how to apply them to these types of exercises.

Answer 1

So you know (or have an idea of) how to find all trees with four vertices. You should find this first. Note that a rooted tree is simply one of these ordinary trees, along with a label placed upon one of the vertices. (Hint: how many rooted trees do you have for each tree? The answer is going to depend on the shape of the tree, but you should be able to say something based on the degrees of the nodes. For instance, the $3$-vertex tree with edges$\{0-1,0-2\}$ will have isomorphic rooted trees when the root is $1$ or $2$, but not when the root is $0$. Why?)

If you prefer to take a more abstract road to the result, or if you happen to be doing this with a computer, there is a method which involves computing the isomorphism groups of your trees, and use them to compute the amount of overcounting done via direct labeling.

There are many other ways to do this problem than the one suggested above. If you are struggling to extend your counting method on ordinary trees to those of rooted trees, you could instead just start with the root node, do casework on its degree, and extend from there. Since you're only dealing with a low number of vertices, this method is also viable.