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?
There is a slick proof using the Euler characteristic formula: if a tree has finitely many nodes then the number of nodes minus the number of edges equals $1$.
You've used $i$ for the number of nodes of degree $d$; to improve visuals, I'll use a capital $I$. I'll also use $L$ for the number of leaves, so the total number of vertices of the tree is $V = I+L$. And let me use $E$ for the number of edges. The Euler characteristic equation becomes $$V-E=1 $$ $$I+L-E=1 $$ which we can solve for $$E = I+L-1 $$ Next we count in an another way. Each edge has two endpoints. Each leaf is counted exactly once in this manner, and each branch node is counted exactly $d$ times. Therefore $$2E = L + d I $$ Now we eliminate $E$: $$2(I+L-1)=L+dI $$ and simplify $$L = (d-2)I+2 $$
Regarding the Euler characteristic formula, the simplest proof I know is an induction proof that is kind of like what you have written.