7
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's a nice style of argument (and it helps me get a better feel for Postnikov's point of view). Thanks for explaining it to me. (By the way, I think Sunday's meeting was officially reckoned as the 60th meeting of the Cambridge Combinatorics and Coffee Club, not the 61st; not that it matters.) $\endgroup$ Nov 4, 2014 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.