Let $F_{n,k}$ be the number of rooted forests with labeled edges with $n$ vertices and $k$ components.
a) Give $F_{n,n}$
b) show that for $k \le n$ we have $F_{n,k-1} = n(k-1)F_{n,k}$
c) conclude that the number of spanning trees of $K_n$ is $n^{n-2}$
I have difficulites to have an understanding of what is even going on here...I thought a bit about it but I am not even sure if any component has to have n vertices or rather the whole graph. Especially confusing I find that $F_{n,k}$ depends on the way the $n$ vertices are distributed on the $k$ components, or doesn't it? If the whole graph has to have $n$ vertices then $F_{n,n}$ is just 1. I don't think thats what they mean, do they? For b) I thought a bit around trying some kind of induction, but it didn't work, it even rather seemed to be just false when I tried it on small examples of graphs with small numbers for $k$ and/or $n$.
As always thanks a lot for your ideas and thoughts.. :)
I don't think the recursive formula is correct.
We know $F_{3,3}=1$: it's the forest where every tree is an isolated vertex, and is a root.
We have $F_{3,2} = 3 \times 2 \times F_{3,3} = 6$. This turns out to be correct. We choose one of three possible edges, and one of its endpoints is a root, and the isolated vertex is a root.
However, according to the formula, we have $F_{3,1} = 3 \times 1 \times F_{3,2} = 18$. This, I believe, is wrong. The 9 rooted labeled spanning forests of $K_3$ are drawn in this paper (p.295). We have a $2$-edge path (3 choices) and a single root ($3$ choices).
Moreover, $F_{3,1}$ is the number of rooted spanning trees of $K_3$, which should be $n$ times the number of (non-rooted) spanning trees of $K_3$, which is given by Cayley's formula as $3$ (part (c) of the question).