1. In the stable marriage problem with three men and three women,
   suppose that all the men have the same preferences as each other, and
   all the women have the same preferences as each other. How many
   different possible solutions to the stable marriage problem will
   there be in this case?

2. Suppose that G is a complete binary tree with four levels and fifteen
   nodes (one root node, two children, four grand-children, and eight
   great-grand-children).
(a) Is G a bipartite graph?
(b) Draw G and show in your drawing a maximum matching (a matching that
    uses as many edges as possible) in G.
(c) How many vertices are there in a minimum vertex cover of G? Show a
    vertex cover with this many vertices.

3. Let H be a graph with six vertices connected into a cycle (a hexagon).
(a) Is H a bipartite graph?
(b) Draw H and show in your drawing a matching that is maximal (cannot
    have any edges added to it) but that is not maximum.
(c) Show an augmenting path for your matching.