We show a new property of Fibonacci numbers which is related to the an
alysis of a very simple and natural parallel tree contraction algorith
m. We show that the size of the smallest tree which requires t contrac
tions equals exactly the tth Fibonacci number. This implies the sharp
bound on the number of iterations of the tree contraction algorithm. W
e contribute also to combinatorics of trees.