Section 10.1: Discrete Mathematics and Its Applications, Extra Examples

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 10.1—Introduction to Trees


p.686, icon at Example 2
#1.
(a) Find the number of nonisomorphic rooted trees with four vertices.
(b) Find the number of nonisomorphic labeled rooted trees with four vertices. (Two trees are isomorphic as
labeled trees if they are isomorphic with vertex i in the first graph corresponding to vertex i in the second
graph.)
(c) Suppose you have four cloth bags — red, blue, green, and yellow. In how many different ways can they
be put inside each other. (For example, the red bag and the yellow bag might be put separately inside the
green bag, and this green bag might then be put inside the blue one, as in the following figure.)

Solution:
(b) The rooted tree A can be labeled in 4! ways. The rooted tree B can be labeled in 4 · 3 ways (there are
four ways to label the root and three ways to label its child; the other two vertices can be labeled in either
order without producing a different tree because the tree is not ordered). The rooted tree C can be labeled
in 4 ways (corresponding to the number of ways of labeling the root). The rooted tree D can be labeled in
4 · 3 · 2 ways (label the root, then label the child that has no descendants, and finally label the child that has
a single descendant). Therefore, the total number of labeled rooted trees is equal to
4! + 4·3 + 4 + 4·3·2 = 64.
(c) There are four patterns according to which the four bags can be placed inside each other — they
correspond to the four nonisomorphic rooted trees in part (a). (For example, the illustration in part (c)
above has the pattern of rooted tree B with “blue” as the root, “green” as its child, and “red” and “yellow”
as the children of “green”.) Therefore, using part (b) of the solution, there are 64 ways in which the bags
can be put inside one another.