A short proof of Cayley's Tree Formula

Research paper by Alok Bhushan Shukla

Indexed on: 09 Oct '09Published on: 09 Oct '09Published in: Mathematics - Combinatorics


A simple combinatorial argument employing symmetry of edges is put forth to establish a recursive relation for counting the number of different labeled trees $T_n$ on $n$ vertices. $T_n = \frac{n}{2} \sum_{k=0}^{n-2} {n-2 \choose k} T_{k+1} T_{n-k-1};$ for n > 1 and $T_1 = 1$ It is proved that $T_n$ calculated from this recursive relation is equivalent to the well known Cayley's Tree Formula $n^{n-2}$.