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
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
with one of my students on the subject.
More recent work yielded
of the Erdős-Ko-Rado and Hilton-Milner theorems.
|