In this problem, we will step through the reasoning behind the formulas

for the number of topologically distinct trees, rooted and unrooted.

a$.$ Suppose we already know that an unrooted tree with n terminal

vertices is made up of e edges. Explain why an unrooted tree with

n $+1$ terminal vertices will have e $+2$ edges. $($Hint: Think about

how adding one more terminal vertex to an existing tree affects the

number of edges.$)$

b$.$ Because an unrooted tree with $2$ terminal vertices has $1$ edge, explain

from part $($a$)$ why an unrooted tree with n terminal vertices will have

$1+2($n $2)=2$n $3$ edges.

c$.$ Suppose we know there are m unrooted trees with n terminal vertices.

Explain why there will be $(2$n $3)$m unrooted trees with n $+1$

terminal vertices. $($Hint: Think about how many different ways you

can add one more terminal vertex to an existing tree.$)$

d$.$ Because there is only $1$ unrooted tree with $2$ terminal vertices, explain

from part $($c$)$ why there are $135(2$n $5)$ unrooted trees

with n terminal vertices when n $>2.$