Bijective proof of an Abel-Hurwitz-type identity

Question

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.

Answer 1

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.