Problem:
Let $T$ be a tree that has $i\ge1$ branch nodes, all of which have the same degree[1] $d$. Show that the number of leaves $(l)$ of the tree can be calculated via the following formula:
$$l=(d-2)i+2$$
[1] The degree of a node is defined as the number of all edges connected to it $(d_{leaf}=1)$.
What I've tried:
I've tried to solve this problem using induction to the number of leaves (I'm open to a better way).
Initial Notes:
- For a node to be a branch node: $d\ge2 \implies d_{min}=2$.
- As a result, the minimum possible number of leaves $l_0=2$.
- Also, let $s=d-d_{min}\ge0$.
So, the formula becomes:
$$
l=(d-d_{min})i+d_{min}
$$
Base Case:
Show that the formula holds for the minimum number of branch nodes $(i=1)$:
$$
l_1=(d-d_{min})\cdot 1+d_{min}=d
$$
The above holds, because the only branch node will be connected to all leaves. $l_1$ can also be written in the following form:
$$
\begin{align}
l_1
&=(d-d_{min})\cdot 1+d_{min}\\
&=l_0+(d-d_{min})\\
&=l_0+s
\end{align}
$$
Inductive Step:
Assume that the formula works for $(i=k)$:
$$
l_k=(d-d_{min})k+d_{min}
$$
Then prove that it works for $(i=k+1)$:
$$
\begin{align}
l_{k+1}
&=(d-d_{min})(k+1)+d_{min}\\
&=(d-d_{min})k+(d-d_{min})\cdot1+d_{min}\\
&=l_k+(d-d_{min})\\
&=l_k+s
\end{align}
$$
Therefore, the formula holds $\forall\ i\ge1$.
Question:
Is my approach correct? If not, what is the best approach to solving this problem?
Best Answer
I'd say the simplest way is to recall that the sum of degrees of all vertices is twice the number of edges, which is $n-1=i+l-1$ for the tree in question. Thus,$$2(i+l-1)=l+di\\\implies l=2+(d-2)i$$