Question

How many nonisomorphic rooted trees are there with six vertices?

Short answer

Therefore, we have 20 nonisomorphic rooted trees with six vertices.

Step-by-step solution

General form

Definition of rooted tree: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Definition isomorphic and nonisomorphic: Two graphs\({{\bf{G}}_{\bf{1}}}{\bf{ = }}\left( {{{\bf{V}}_{\bf{1}}}{\bf{,}}{{\bf{E}}_{\bf{1}}}} \right)\) and \({{\bf{G}}_{\bf{2}}}{\bf{ = }}\left( {{{\bf{V}}_{\bf{2}}}{\bf{,}}{{\bf{E}}_{\bf{2}}}} \right)\)are isomorphic if there exists a one-to-one and onto functions\({\bf{f:}}{{\bf{V}}_{\bf{1}}} \to {{\bf{V}}_{\bf{2}}}\) such that \(\left( {{\bf{a,b}}} \right) \in {{\bf{G}}_{\bf{1}}}\) if and only if \(\left( {{\bf{f}}\left( {\bf{a}} \right){\bf{,f}}\left( {\bf{b}} \right)} \right) \in {{\bf{G}}_{\bf{2}}}\) for all a and b in \({{\bf{V}}_1}\). such a function f is called an isomorphism.Two simple graphs that are not isomorphic are called nonisomorphic.

Evaluate the nonisomorphic rooted tree

A nonisomorphic rooted tree with 6 vertices has height 1, 2, 3, 4, or 5.

Case (1): Height 5

There is only one possible nonisomorphic rooted tree with height 5, which is the rooted tree that represents a Path of length 5. The tree is shown below.

Case (2): Height 4

There are 4 possible nonisomorphic rooted tree with height 4 (whose longest path has length 4), because we need to attach the leaf of the rooted tree with a path of length 5 to one of the top four vertices.

Note: we can’t attach it to the 5^th vertex, as that would result in tree with height 4.

The trees are shown below.

Evaluate the nonisomorphic rooted trees

Case (3):Height 3

There are 8 possible nonisomorphic rooted tree with height 3 (whose longest path has length 3), because if we start from a path with length 3, then we can attach the last two vertices to the same vertex of the top three vertices, we could attach the last two vertices to a different vertex of the top three vertices and we can attach the last two vertices in a path of length 2 to one of the top two vertices.

That is, \({\bf{3 + 3 + 2 = 8}}\).

The trees are shown below.

Case (4): Height 2

There are 6 possible nonisomorphic rooted tree with height 3 (whose longest path has length 3), because if we start from a path with length 2, then we can attach the last three vertices to the same vertex of the top two vertices, we could attach the two of the last two vertices to one of the top two vertices and remaining vertex to the other vertex among the top two vertices and we can attach two of the remaining three vertices as a path of length 2 to the root and then the remaining vertex can be attached to the root of a vertex at level 1.

That is, \(2{\bf{ + }}2{\bf{ + 2 = }}6\).

The trees are shown below.

Case (5): Height 1

There is only one possible nonisomorphic rooted tree with height 1 (whose longest path has length 1), because 5 vertices have to all be connected to the root.

The tree is shown below.

Conclusion: So, the total of nonisomorphic we note that the trees with 6 vertices are 20. That is, \({\bf{1 + 4 + 8 + 6 + 1 = 20}}\).