3
$\begingroup$

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.

  • 0
    I found [this question](http://math.stackexchange.com/questions/86492/number-of-leaves-in-a-tree-all-types-of-trees) while searching for duplicates, the notations are close but not exactly the same plus that my question is about binary trees.2011-12-17
  • 0
    Do you mean there are $n_i$ nodes of degree $i$? What do you mean by degree BTW?2011-12-17
  • 0
    @AliBleybel: For instance, $n_0$ is the number of leaves, nodes of degree 0.2011-12-17
  • 0
    You should check your notation: the terms left of '...' do not correspond to those on the right (or you'd have 2n_3 + n_1 as coefficients); and the double n_2 at the end seems wrong too.2011-12-17
  • 0
    @gnometorule: Right, sorry about that.2011-12-17
  • 0
    You probably should prove this with induction, and it shouldn't be so hard...however, the statement as is (or the way I understand it) can't be right. Look at an easy case: complete binary tree with 4 leaves. In your notation the way I understand it, the tree has2011-12-17
  • 0
    n_0 = 4; n_1 = 2; n_2 = 1. This would make the equation 4 = 2. So in this case, keeping the other terms as is, we'd need to add also n_1 on the right. For the next complete binary tree, we get n_0 = 8; n_1 = 4; n_2 = 2; n_3 = 1, and so - per the above formula - 8 = 4.2011-12-17
  • 0
    If my understanding of your notation is correct, then I believe the right formula is n_0 = n_1 + n_2 + ... + n_k + 1 (which is essentially just the geometric sum).2011-12-17
  • 0
    @gnometorule: in your case (complete binary tree with 4 leaves), $n_1=0$ and $n_2=3$, then 4=4 and it holds. The point is, number leaves is independent of nodes of degree one ($n_1$).2011-12-17
  • 0
    In normal graph-theoretic terms a leaf has degree $1$, not $0$, and all nodes in a binary tree have degree $1$, $2$, or $3$, so you must be using *degree* in some other way. Exactly how are you defining *degree*?2011-12-17
  • 0
    @BrianM.Scott: I believe that "degree" in my book is defined as number of children a node has.2011-12-17
  • 0
    Yes, 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 1

3

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 $km$, so

$$ \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
    Actually, I don't get how you got the result $\sum_{k\ge 1}(k-1)n_k(T)=\sum_{k\ge 1}(k-1)n_k(T\,')+1\ $ from the previous line, and then the other line after it.2011-12-17
  • 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