Parallel Tree-Contraction and Fibonacci Numbers

We show a new property of Fibonacci numbers which is related to the analysis of a very simple and natural parallel tree contraction algorithm. We show that the size of the smallest tree which requires t contractions equals exactly the t-th Fibonacci number. This implies the sharp bound on the number of iterations of the tree contraction algorithm. We contribute also to combinatorics of trees