Question

Draw the 16 labeled trees on 4 vertices.

Answer 1

These 16 labeled trees are shown in Figure 5.1.

The distinction between a labeled and an unlabeled graph is very important when we are counting the number of different possible graphs . For instance, the four graphs in the first row of figure 5.1 are counted as four different trees because the vertices are labeled differently even though the trees are isomorphic. If there were no distinction made between A,B,C and D , these four trees would be counted as one . A careful inspection of the graphs in figure 5.1 revels that there are only two unlabeled trees on four vertices with no distinction made between A,B,C and D