$(ii)$ Ignoring vertex labels, how many distinct trees are there with $5$ vertices? Draw each such tree, and justify your conclusion that there are no more. $(iii)$ Choose one of the trees that you drew in $(ii)$, and call this tree $T$. How many copies of $T$ are there in $K_{10}$?
$(ii)$ I figured out there are $3$ but how can I prove there are no more. Also, is there a way to do this without trial and error. I considered the degree sequences and that the only possible degree were sequences were $(1,1,2,2,2) , (1,1,1,1,4) , (1,1,1,2,3)$ since only max degrees of a tree are $2,3,4$. This gave me:
$(iii)$ Let $T$ be donted as above in the image. This is a copy of $P_4$. $K_{10}$ has $10$ vertices. For the middle vertex of $T$, there are $10C1$ possibilities. For the two endpoints, there are $9C2$ possibilities of the $9$ remaining vertices of $K_{10}$. Multiplying we get $360$. Is this correct ? How would I count the number of ways if I chose tree $2$ or $3$ as $T$ instead ?
Thanks.
Hints about classifying trees on the order of $5$.
If the degrees of the vertices of the tree do not exceed $2$, then it is a path. It doesn't matter how many vertices there are.
If a tree has a vertex of degree $3$, then it has at least three leaves, in our case exactly $3$.
In general, if a tree has a vertex of degree $d$, then it has at least $d$ leaves. The case $d=4$ is important for us.