Trees Problem 3


Notice that we are proving only a lower bound on the number of spanning trees. You need a procedure that identifies f(n) spanning trees in the n-dimensional hypercube. But you don't need to worry about the possibility that there might be other spanning trees not generated by your procedure.

Double-check what the smallest hypercube looks like, since that will be your base case.

The proof should use strong induction that follows the recursive definition of \(Q_n\). For example

The proof will require that you construct a whole set of spanning trees and count how many you've constructed. Before you try that, however, figure out how to build a single one. Start with \(Q_4\). It contains two copies of \(Q_3\). Find a spanning tree for each one. How can you use these to make a spanning tree for \(Q_4\)?

Once you know how to make spanning trees, count up how many ways you can construct one. Where did you get to make a choice (e.g. pick something out of a set)? How many options did you have for that choice? Where else did you get to make a choice?

When you're trying to count up the number of choices, it's fine to peek at the formula for f(n). That's what you're trying to match, right?