# proof of cayley's theorem; graph theory

• September 8th 2011, 07:53 AM
abhishekkgp
proof of cayley's theorem; graph theory
Consider the recursion:
$f(n)=\sum_{k=1}^{n-1} (-1)^{k+1} {n \choose k} (n-k)^k f(n-k)$
Where $n \geq 3, f(1)=f(2)=1$.

I got this recursion when i tried to prove the cayley's theorem which says that there are $n^{n-2}$ distinct labelled trees on $n$ vertices.
I have checked that $f(n)=n^{n-2}$ satisfies the equation for $n=3,4,5,6$. Any idea how to prove that the solution to this recursion is $f(n)=n^{n-2}$.
• September 15th 2011, 09:21 AM
Traveller
Re: proof of cayley's theorem; graph theory
I don't have a solution but could you please explain how you got that recursion?