I want to prove $n_0=(k-1)n_k+(k-2)n_{k-1}+\dots+3n_4+2n_3+n_2+1$ for T as a binary tree where $n_i$ is nodes of degree $i$. I tried to prove it using the handshake lemma but came up with nothing useful.
Prove $n_0=(k-1)n_k+(k-2)n_{k-1}+\dots+3n_4+2n_3+n_2+1$
-
0Yes, I just realized that that must be it. And the theorem is true for all trees, not just binary trees. I’ll write up an answer in a minute. – 2011-12-17
1 Answers
We want to prove that if $T$ is any tree, and $n_k(T)$ is the number of nodes of $T$ with $k$ children, then $n_0(T)=1+\sum_{k\ge 2}(k-1)n_k(T)\;.\tag{1}$ Note for future reference that the righthand side can be written $1+\sum_{k\ge 1}(k-1)n_k(T)\;,$ since the $k=1$ term is $0$.
Added: I realized after I went to bed that there’s a short argument that doesn’t use induction. Let $T$ be a tree with $n$ vertices and $e$ edges. Then $n=\sum_{k\ge 0}n_k(T)\;,$ and $e=\sum_{k\ge 1}kn_k(T)\;,$ since a non-leaf node with $k$ children produces $k$ edges connecting it to those children. But in any tree $n=1+e$, so $\sum_{k\ge 0}n_k(T)=n=1+e=1+\sum_{k\ge 1}kn_k(T)\;,$ and subtracting $\sum\limits_{k\ge 1}n_k(T)$ from both sides leaves $n_0(T)=1+\sum_{k\ge 1}kn_k(T)-\sum_{k\ge 1}n_k(T)=1+\sum_{k\ge 1}(k-1)n_k(T)\;.$ I’ve kept the original proof below, however, as it embodies a useful technique.
This can be done by induction on the number of nodes in $T$. It’s clearly true for the tree with just one node, since in that case it says that $1=1$. Suppose that $n>1$, and it’s true for all trees with fewer than $n$ nodes. Let $T$ be a tree with $n$ nodes, and let $v$ be any leaf of $T$. Since $n>1$, $v$ is not the root of $T$; let $u$ be the parent of $v$, and let $m$ be the number of children of $u$. Let T\,' be the tree obtained from $T$ by removing the leaf $v$ and its adjacent edge. There are two possibilities.
If $m=1$, $u$ is a leaf of T\,', and n_0(T\,')=n_0(T). But this is fine: the only vertex whose number of children changed in passing from $T$ to T\,' is $u$, and it had only one child to begin with, so it wasn’t counted in $(1)$ anyway, and therefore 1+\sum_{k\ge 1}(k-1)n_k(T)=1+\sum_{k\ge 1}(k-1)n_k(T\,')\;. Thus, n_0(T\,')=n_0(T)=1+\sum_{k\ge 1}(k-1)n_k(T)=1+\sum_{k\ge 1}(k-1)n_k(T\,')\;, as desired.
If $m>1$, the tree loses a leaf without gaining one, and n_0(T)=n_0(T\,')+1. It also loses a node with $m$ children but gains one with $m-1$ children, so n_m(T)=n_m(T\,')+1\;, and n_{m-1}(T)=n_{m-1}(T\,')-1\;. Thus,
\begin{align*} (m-2)n_{m-1}(T)+(m-1)n_m(T)&=(m-2)\big(n_{m-1}(T\,')-1\big)+(m-1)\big(n_m(T\,')+1\big)\\ &=(m-2)n_{m-1}(T\,')+(m-1)n_m(T\,')+1\;. \end{align*}
n_k(T)=n_k(T\,') for $k
\begin{align*} \sum_{k\ge 1}(k-1)n_k(T)&=\sum_{k=1}^{m-2}(k-1)n_k(T)\\ &\qquad\qquad+(m-2)n_{m-1}(T)+(m-1)n_m(T)\\\\ &\qquad\qquad+\sum_{k>m}(k-1)n_k(T)\\ &=\sum_{k=1}^{m-2}(k-1)n_k(T\,')\\ &\qquad\qquad+(m-2)n_{m-1}(T\,')+(m-1)n_m(T\,')\color{red}{+1}\\\\\ &\qquad\qquad+\sum_{k>m}(k-1)n_k(T\,')\\ &=\sum_{k\ge 1}(k-1)n_k(T\,')\color{red}{+1}\;. \end{align*}
Thus, \begin{align*} n_0(T)=n_0(T\,')+1&=\left(1+\sum_{k\ge 1}(k-1)n_k(T\,')\right)+1\\ &=1+\left(\sum_{k\ge 1}(k-1)n_k(T\,')\color{red}{+1}\right)\\ &=1+\sum_{k\ge 1}(k-1)n_k(T)\;, \end{align*} again as desired.
-
0@Gigili: I’ve added some extra detail to help with the first bit and fixed the typo that probably caused you trouble with the last bit. I’ve also added a shorter, non-inductive proof that occurred to me after I went offline. – 2011-12-17