Article - postprint
We present a combinatorial proof that the wheel graph Wn has L2n − 2 spanning trees, where Ln is the nth Lucas number, and that the number of spanning trees of a related graph is a Fibonacci number. Our proofs avoid the use of induction, determinants, or the matrix tree theorem.
© 2006 Institute of Combinatorics & Its Applications
A. Benjamin, C. Yerger, Combinatorial Interpretations of Spanning Tree Identities, Bulletin of the Institute for Combinatorics and its Applications, Vol. 47, 37-42, 2006.