Discrete Mathematics: Elementary and Beyond

8.5 The Number of Unlabeled Trees 155

as 1’s). Still, the planar code is quite an efficient way of encoding unlabeled
trees: It uses less than 2nbits for trees withnnodes. Since there are more
than 2nunlabeled trees (at least forn>30), we could not possibly get by
with codes of lengthn: there are just not enough of them.
In contrast to what we know for labeled trees, we don’t know a simple
formula for the number of unlabeled trees onnnodes, and probably none
exists. According to a difficult result of George P ́olya, the number of un-
labeled trees onnnodes is asymptoticallyan−^5 /^2 bn, wherea=0. 5349 ...
andb=2. 9557 ...are real numbers defined in a complicated way.

8.5.1Does there exist an unlabeled tree with planar code

(a) 1111111100000000; (b) 1010101010101010; (c) 1100011100?

Review Exercises

8.5.2LetGbe a connected graph, andean edge ofG. Prove thateis not a
cut-edge if and only if it is contained in a cycle ofG.

8.5.3Prove that a graph withnnodes andmedges has at leastn−mconnected
components.

8.5.4Prove that if a tree has a node of degreed, then it has at leastdleaves.

8.5.5Find the number of unlabeled trees on 6 nodes.

8.5.6Adouble staris a tree that has exactly two nodes that are not leaves.
How many unlabeled double stars are there onnnodes?

8.5.7Construct a tree from a path of lengthn−3 by creating two new nodes and
connecting them to the same endpoint of the path. How many different labeled
trees do you get from this tree?

8.5.8Consider any table with 2 rows andn−1 columns; the first row holds
1 , 2 , 3 ,...,n−1; the second row holds arbitrary numbers between 1 andn. Con-
struct a graph on nodes labeled 1,...,nby connecting the two nodes in each
column of our table.

(a) Show by an example that this graph is not always a tree.

(b) Prove that if the graph is connected, then it is a tree.

(c) Prove that every connected component of this graph contains at most one

cycle.

8.5.9Prove that in every tree, any two paths with maximum length have a node
in common. This is not true if we consider two maximal (i.e., nonextendable)
paths.