We have noted in this section that there are nn2 labeled tre

We have noted in this section that there are nn-2 labeled trees on n vertices. (a) Verify this formula for n = 4 by drawing the nonisomorphic unlabeled trees on four vertices and discovering how many different labeled trees the determines. (b) Repeat (a) for n = 5. (a) Non isomorphic unlabeled trees with four vertices can be drawn as: The tree on the right determines 4/2 = 12 distinct labeled trees. And from the left tree we can derive 4 labeled trees. So, in all there can be 16 such labeled trees. We can see that 16=4 \", which is in agreement with the formula (b) Non isomorphic unlabeled trees with five vertices can be drawn as: The tree on the left determines 5/2 = 60 distinct labeled trees. The tree on the right gives 5 labeled trees. And to label the middle tree, we have to assign a label to the vertex of degree 3 (in one of five ways). Then labels for the two vertices of degree 1 below can be chosen in (4/2) = 6 ways.

Solution

First explaining Step 3

The tree on the right determines 4!/2= 12 distinct labeled trees.

Here, concept of permutation and combination is used as there are 4 vertices shown in the tree on the right where there is a connection between pairs and in a line due to which it is 4!/2.

And, from the left tree we can derive 4 labeled trees as here also the same concept is used. Here, the 4 vertices are connected with one in the centre and rest 3 connected with it. So, all 4 can come in the centre one by one and therefore, we have 4 labeled trees.

Now explaining Step 5

The tree on the left determines 5!/2= 60 distinct labeled trees.

Here, concept of permutation and combination is used as there are 5 vertices shown in the tree on the right where there is a connection between pairs and in a line due to which it is 5!/2.

From right tree we can derive 5 labeled trees as here also the same concept is used. Here, the 5 vertices are connected with one in the centre and rest 4 connected with it. So, all 5 can come in the centre one by one and therefore, we have 5 labeled trees.

To label the middle tree, you have to assign a label to the vertex of degree 3 as all 5 vertices can come at that place one by one (in one of 5 ways).

Then, labels for the two vertices of degree below can be chosen in 6 ways as you can select two for that position.

Now, finally two labels are left which can be assigned in 2 ways.

Hence, middle tree gives total of 5*6*2= 60 ways.

Therefore, total = 125 distinct labeled trees which satisfies the formula.

Hope, now everything is clear to you.