Spanning Trees and Aspects (The 15th Annual Christmas Tree Lecture) December 8, 2009

Computer Musings with Don Knuth

The spanning trees of a graph with n vertices are the sets of n-1 edges that connect the graph. In this lecture I'll discuss the remarkable relation between the number of spanning trees and the aspects of the graph, which are defined via matrix theory. For example, I'll explain why the number of spanning trees of an n-dimensional cube is equal to exactly $2^{2^n-n-1} \prod_{k=1}^n k^{n\choose k}$.

Official Website: http://www-cs-faculty.stanford.edu/~knuth/musings.html