How do I represent the possible trees and formula for this question?

Question

If all the vertices in a tree have degree 1 or 5, how many vertices and leaves can it have? Suppose the tree has n vertices. Give a formula for the possible values of n and express the number of leaves in terms of n.

Answer 1

Hint: use the handshake lemma.

If a tree has $l$ leaves and $k$ vertices of degree $5$, then $l+k=n$ and by the handshake lemma $l+5k=2n-2$. Therefore the number of leaves is \begin{align}l=\frac{3n+2}{4}.\end{align} Therefore $3n+2\equiv 0 (\operatorname{mod} 4)$ which gives $n=4j+2$ for $j\in\mathbb N\cup\{0\}$ as the possible values for $n$. It is not difficult to see (e.g. by induction) that for all $j\in\mathbb N\cup\{0\}$ such a tree exists.