# 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?