Warning: jsMath requires JavaScript to process the mathematics on this page.
If your browser supports JavaScript, be sure it is enabled.

G. Hurlbert Bijections
Bijections

Cayley proved that there are $n^{n-2}$ labeled trees on $n$ vertices, which is the same as saying there are that many spanning trees of the labelled complete graph. Prufer gave a distinct name to each of them, exhausting all possible $n$-ary $(n-2)$-tuples as names, thus giving a bijective proof of Cayley's result. An old paper gives a new bijection for the number of spanning trees of labeled complete $r$-partite graphs, and discusses a number of other graphs whose spanning trees I covet to biject (cubes, deBruijn graphs, and integral graphs such as the Petersen graph among them). I am also fond of lattice paths and I have written a paper with one of my students on the subject. More recent work yielded bijective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems.