Document Type
Article - postprint
Department
Mathematics (HMC)
Publication Date
2006
Abstract
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.
Rights Information
© 2006 Institute of Combinatorics & Its Applications
Terms of Use & License Information
Recommended Citation
A. Benjamin, C. Yerger, Combinatorial Interpretations of Spanning Tree Identities, Bulletin of the Institute for Combinatorics and its Applications, Vol. 47, 37-42, 2006.
