Bijections for Cayley trees, spanning trees, and their q-analogues (Q1077424): Difference between revisions

Let \(C_ n\) denote the set of Cayley trees on the vertex set \(\{\) 1,2,...,n\(\}\) and \(C_{n,i}\) the rooted Cayley trees of this kind with root i. Bijective proofs for Cayley's classical formula \(| C_{n+1}| =| C_{n+1,i}| =(n+1)^{n-1}\) for all \(n\geq 1\) and \(i=1,...,n+1\) have been given by Prüfer and, via a special encoding, by Joyal. In this paper a new bijective proof is given. The weight preserving properties of the family of bijections in use allow to derive a number of other results, too, and by the same idea bijective proofs and q-analogues for the number of spanning trees of other graphs are established.