Can anyone sketch for me a bijective proof of the fact that the number of spanning trees of the complete graph on $n$ vertices, $K\_n$ (given by the formula $ t\_n = n^{n-2}$), satisfies $ t\_n = \frac{n}{2} \sum\_{k=1}^{n-1} {n-2 \choose k-1} t\_{k} t\_{n-k} $? Sasha Postnikov suggested that I take a look at <http://math.mit.edu/~apost/papers/AbelHurwitz.pdf>
 but despite a fairly strong resemblance between his identities and mine I don't see how to link them.



Bijective proof of an Abel-Hurwitz-type identity
I believe this is the proof Postnikov suggested at CCCC LXI. Let us say that $K\_n$ has vertices $1,2,\ldots,n$. Imagine a spanning tree of $K\_n$ as being rooted at $1$. To any spanning tree $T$, we associate $T'$, the part of the tree at or below the vertex $2$ in this tree, and $T''$, the other part of the tree (which at least contains the root vertex $1$). Say $|T'| = k$ with $1 \leq k \leq n-1$. Then there are $\binom{n-2}{k-1}$ possible sets of labels for $T'$, $t\_k$ possible trees for $T'$ given such labels, $t\_{n-k}$ trees for $T''$ (whose set of labels is now determined), and $n-k$ places to "stick" $T'$ into $T''$ (which amounts to a choice of which vertex in $T''$ the vertex $2$ is a child of). This proves
$$t\_n = \sum\_{k=1}^{n-1} (n-k) \binom{n-2}{k-1} t\_k t\_{n-k}.$$


Your equation then follows by grouping the term $k$ with the term $n-k$ in that sum, and then redistributing.


