# proof about a recursive tree and leaves and number of vertices

Let $T$ be a tree whose vertices are the integers $1$ through $n$. We call $T$ a recursive tree if it has the following special property. Let $P$ be any path in $T$ starting at vertex $1$. Then, as we move along the path $P$, the vertices we encounter come in increasing numerical order. Please do the following:

• a. Prove: If $T$ is a recursive tree on $n$ vertices, then vertex $n$ is a leaf (provided $n>1$).
• b. Prove: If $T$ is a recursive tree on $n>1$ vertices, then $T-n$ (the tree $T$ with vertex $n$ deleted) is also a recursive tree (on $n-1$ vertices).
• c. Prove: If $T$ is a recursive tree on $n$ vertices and a new vertex $n + 1$ is attached as a leaf to any vertex of $T$ to form a new tree $T\,'$, then $T\,'$ is also a recursive tree.
• d. How many different recursive trees on $n$ vertices are there? Prove your answer.

I am not sure where to start on these proofs or how to prove them. I tried starting with the definition of a tree but I am not sure how to get to the desired results.

-
Ali: If you click on the time next to 'edited' and then click on 'source' for my edit, you'll see what I typed to get the formatting that you wanted. (Or you can simply click here.) – Brian M. Scott May 2 '12 at 17:37

a) Assume $n$ is not a leaf. Then it has a child. Therefore there is a path from 1 to the child, and this path is not in increasing order ($n$ is the largest element but not the last in the path). This is a contradiction.

b) By a) $n$ is a leaf. Therefore if you remove it, $T$ is still a tree. Furthermore, only paths including $n$ are affected by its removal. All paths that include $n$ must end at $n$, so they remain in order when $n$ is removed.

c) $T'$ is a tree. Furthermore, any path $P$ from 1 to $n+1$ must end on $n+1$, as it is a leaf. If this path is truncated before $n+1$ it must be in increasing order as $T$ is a recursive tree. $n+1$ is larger than any element in $T$, therefore $P$ is in increasing order. $T'$ is therefore a recursive tree.

d) Construct a recursive tree by adding nodes as leaves using the process in part c. When adding node $n$ you have $n-1$ possible parent nodes you can add $n$ as a leaf to. All recursive trees can be constructed this way (proof follows below). Therefore for a tree of $n$ nodes, there are $(n-1)!$ possible trees.

To show that every recursive tree can be constructed this way, note that any tree where the parent of each node has a lower value than all of its children (and subchildren) can be constructed this way (all nodes with a lower value will already be placed, therefore the parent will be in the tree, so you can attach the new node). Therefore all such trees are recursive trees by part c. Furthermore, if a node has a higher value than one of its descendants, there exists a path from $1$ to that descendant that is not in order. So every recursive tree can be constructed this way.

-

I recommend a contrapositive approach for (a) and (b), and a direct approach for (c).

For (a), suppose $T$ is a tree on $n$ vertices ($n>1$) and that $n$ is not a leaf. What does it mean that $n$ isn't a leaf? Is it possible for $T$ to be recursive in that circumstance?

For (b), suppose that $T-n$ isn't recursive. What does that mean? Is it possible for $T$ to be recursive?

For (c), take any path in $T'$ starting at 1. There are only 2 possibilities: $n+1$ is on the path or it isn't. If $n+1$ is not on the path, it's a path in $T$. If $n+1$ is on the path, then use the fact that $n+1$ is a leaf to show that it must simply be added on to the end of a path in $T$. Using this, and the fact that $T$ is recursive, show that $T'$ is recursive.

For (d), suppose there are $k_n$ recursive trees with $n$ vertices (what is $k_1$?). Given any recursive tree $T$ on $n$ vertices, to how many vertices of $T$ can we adjoin a vertex $n+1$ to get a tree $T'$, (which will be recursive by (c))? If $T_0$ and $T_1$ are two different recursive trees on $n$ vertices, and if $T_0'$ and $T_1'$ are recursive trees on $n+1$ vertices formed as in (c), is it possible for $T_0'$ and $T_1'$ to be the same? Are there any trees on $n+1$ vertices that can't be obtained as in (c) from a tree on $n$ vertices?

-