# Trees Problem 3

### Hints

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

• When your inductive step considers a hypercube of dimension k, divide it into two hypercubes of dimension k-1.
• Your procedure for constructing free trees that span the big hypercube $$Q_k$$ should use the sets of free trees constructed for each of the smaller hypercubes (i.e. the two copies of $$Q_{k-1}$$).

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?