Proof: Suppose (for sake of contradiction) that n is not a leaf, but instead has at least two neighbors.There is a unique path from 1 to n in T, which includes exactly one neighbor of n.Let v be the neighbor of n not on this path.So, n lies on the unique path from 1 to v.But v < n, so this is a contradiction.

(a)Prove that if T is a recursive tree on n vertices, and n >1, then the tree Tn is also a recursive tree.

(b)Prove that if T is a recursive tree on n vertices, and n >1, and a new vertex n+ 1 is attached as aleaftoanyvertexof T toformanewtree T,then T isalsoa recursive tree.

(c)How many different recursive trees on n vertices are there?Prove your answer using Mathematical Induction.