I'd like to prove the equation following:

$$x_1x_2x_3...x_n(x_1 + x_2 + ... x_n)^{n-2} = \sum_Tx_1^{d_{T(1)}}x_2^{d_{T(2)}}...x_n^{d_{T(n)}}\tag 1$$

where the sum is over all spanning trees $T$ in $K_n$ and $d_{T(i)}$ is the degree of $i$ in $T$

I heard this's called Cayley's generalized formula, which is the number of $trees$ in $n$ vertices:

$n^{n-2} \tag 2$

Only the morphological similarity between $(1)$ and $(2)$ is the power $n-2$.

I think in this case induction might work well, but honestly $induction$ itself is not a productive way of proving something to reveal one's mathematical identity to me including this case, proof of $(1)$.

Any hint to prove this equation in combinatoric and algebraic way?


Let's divide both sides of $(1)$ by $x_1\dots x_n$, then we have to prove $$ (x_1 + x_2 + \dots + x_n)^{n-2} = \sum_{T}x_1^{d_{T(1)}-1}x_2^{d_{T(2)}-1}\dots x_n^{d_{T(n)}-1}. $$ But now the argument is basically the same as Prüfer's proof. Note that each vertex $T(i)$ occurs $d_{T(i)}-1$ times (the number of steps in Prüfer's algorithm it takes for $T(i)$ to become a leaf) in the corresponding Prüfer's sequence, which has total length $n-2$. On the other hand, each term in the Prüfer's sequence can take any value from $1$ to $n$, so it corresponds to a factor of $x_1+\dots+x_n$. We have $n-2$ such factors, which yields the left-hand side. To derive $(2)$ from $(1)$, simply let $x_1=\dots=x_n=1$.


As you might have noticed, setting all the $x_i$ to $1$ recovers the fact that the number of trees on $n$ vertices, which is the same as the number of trees spanning $K_n$, is $n^{n-2}$.

To get a bijective proof of (1), let $x_1, \ldots, x_n$ be numbers labeling the vertices of $K_n$. Given a spanning tree $T$, note that $$\prod_{(i,j) \in T} x_ix_j = \prod_{i = 1}^n x_i^{d_i(T)}.$$ (The product on the left is over edges of $T$.)

Summing over all spanning trees $T$, we are reduced to showing that $$\sum_{T} \prod_{(i, j) \in T} x_ix_j = x_1x_2\ldots x_n(x_1 + x_2 + \ldots + x_n)^{n-2}.$$

Note that the right hand side is the sum over all monomials of degree $2n-2$ in which each variable has degree at least $1$. Now, given any set $S$ of $n-1$ edges $(u_i, v_i)$ in $K_n$, we can form the degree $2n-2$ monomial $$m(S) = \prod_{i=1}^{n-1} x_{u_i}x_{v_i}.$$ Moreover, if $S$ happens to be a spanning tree, each variable will appear at least once.

To complete the proof, it suffices to show that $m$ is a bijection between the set of spanning trees and monomials of degree $2n-2$ in which each $x_i$ occurs at least once. Can you take it from here?

  • $\begingroup$ could you give me a hint how to prove m constructs bijection between spanning trees and monomials? $\endgroup$ – Beverlie Dec 6 '17 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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