Question: 1. Show that a graph is connected if and only if it has a spanning tree.
2. How many different binary search trees can be made with three pieces of data? What about with four pieces of data?
3. The tree of partial solutions could have had as many as 1+8+64+...88 = 19,173,961 nodes.
(a) We knew that node (2,2) corresponded to a non-solution. How many nodes did we remove from the tree by removing (2,2)?
(b) We also know that (2,1),(2,3), and all other pairs of the form (k,k - 1),(k,k),(k,k+1) correspond to non-solutions. How many such nodes are there?
(c) How many nodes, total, does removal of these length-2 nodes cause to be removed?
(d) So, just removing the length-2 nodes that we know are no good, how many nodes are left in the tree of partial solutions?