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.