Chris Hanusa  Math 381 – Homework 3 Answer Key  Nov 14, 2003

Question 1 – Find the tree which has the following father code: 9 9 10 10 9 0 0 0 10 0 .

Answer: It’s easier to see this once we add numbers above the father code:

1 2 3 4 5 6 7 8 9 10

9 9 10 10 9 0 0 0 10 0

To start, we take the root 0 and connect it to vertices 6,7,8, and 10. Then we connect vertex 10 to vertices 3,4, and 9. Lastly, we connect vertex 9 to vertices 1,2, and 5. So we have a tree that looks like

8  3  1
|  |  |
7 − 0 − 10 − 9 − 5
|  |  |
6  4  2

Question 2 – If you have a father-code of a tree, how can you figure out the degree-sequence of the tree without drawing the tree (i.e. using only the code). Answer: The number of times a point appears on the bottom row of the father code is the number of points that this point is a father to. In addition, it must be the son of some other point (except for the root). Lastly, each point occurs once on the top row of the father code except the root, which is not a son of any other point, there are two ways to represent the degree of each vertex.

The degree of each vertex is the the number of times it appears in both rows of the father code. It is also the case that the degree of each vertex is the number of times it appears in the bottom row of the father code plus 1 except for the root, in which case it is just the number of times that 0 appears in the father code.

Question 3 – Find the Prufer-code of the labelled tree which you have reconstructed in the first problem.

Answer: Using the method described on page 16 of the notes part II, we find that the Prüfer code is 9 9 10 10 9 0 0 0 10. Note that there is no top row and no ending zero.

Question 4 – Give a planar code of the tree in the first problem. (Remember, the planar code is for unlabelled trees.) How many different planar codes can you get for this tree? What can you say in the general case?

Answer: One planar code for this tree starts at 7 and goes around counterclockwise: 1101101101010010100. There are four distinct planar codes for this tree because of the symmetries. They are

(1) Starting at 6, going counter-clockwise

(2) Starting at 7, going counter-clockwise

(3) Starting at 8, going counter-clockwise

(4) Starting at 3, going counter-clockwise

The tree can be written in two different ways (depending if the central vertices are one up and one down or both below the central axis), the second case has no symmetry (except the one rotation), so there are 8 ways to write the planar code, starting at each leaf and going counter-clockwise.

So counting both ways to write the tree, there are 12 = 4+8 different planar codes for this tree.

In the general case, we know that there are at most 2 times the number of leaves of the tree, but the number may be fewer if there is symmetry.

   [NOTE: Remember that planar codes start only on leaves.]