Donald Knuth: Finding All Spanning Trees

The 10th Annual Christmas Tree Lecture

The spanning trees of a graph or network of npoints are the ways to connect those points by choosing n-1 of the available point-to-point interconnections. I will discuss an interesting procedure by which we can run through all possible spanning trees in such a way that only one branch of the tree is changed at every step. The method is particularly nice when the given graph is a series--parallel network