2012/08/20 by Chestnut, Stephen R., Fishkind, Donniell E.
#05A19 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1208.4125
Cayley's formula states that there are nn-2 spanning trees in the complete graph on n vertices; it has been proved in more than a dozen different ways over its 150 year history. The complete graphs are a special case of threshold graphs, and using Merris' Theorem and the Matrix Tree Theorem, there is a strikingly simple formula for counting the number of spanning trees in a threshold graph on n vertices; it is simply the product, over i=2,3, ...,n-1, of the number of vertices of degree at least i. In this manuscript, we provide a direct combinatorial proof for this formula which does not use the Matrix Tree Theorem; the proof is an extension of Joyal's proof for Cayley's formula. Then we apply this methodology to give a formula for the number of spanning trees in any difference graph.