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

G. Hurlbert 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. My recent 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 while we are working on another.