MATH/CSCI 2113
Assigment 6
Due Wednesday, March 6, at the beginning of class.

For each of the following problems, show your work.

1. Do problem 11.3.28 on page 505 of the book. Explain your answer.

2. Consider the hypercubes $Q_n$ (see Example 11.12 on page 496 of your text book).

   (a)

   For what values of $n$ does $Q_n$ have an Euler circuit? Explain your answer.

   (b)

   Does $Q_3$ have a Hamilton cycle? If not, explain why not. If so, give the Hamilton cycle.

   (c)

   For what values of $n$ does $Q_n$ have a Hamilton cycle? Explain your answer.

3. Prove the following statement: any connected graph with $n$ vertices and $n-1$ edges is a tree.

4. Prove the following statement: any acyclic graph with $n$ vertices and $n-1$ edges is connected. Hint: proof by contradiction.

5. Use strong induction to prove the following statement: every tree has at least two pendant vertices. Hint: look at the proof in the text book that a tree with n vertices has n-1 edges.

6. Consider the two graphs in Figure 12.6 on page 552 of the text book. (a) Determine how many different spanning trees each of these graphs has (you do not need to draw them). (b) For graph (1), how many non-isomorphic spanning trees are there? Draw one of each type.

7. Do problem 12.2.6 on page 569 of the text book.