Due in lecture, Thursday June 13. Please do the homework in a workbook.

# From the Text

Complete the following questions from the text:

- Section 9.1: 28.
- Section 9.2: 26, 54.
- Question 26: \(W_n\) is defined on page 601.
- Question 54: \(\overline{G}\) is defined above question 53.

- Section 9.3: 22, 28.
- Section 9.4: 18, 26.
- Question 18: or make any other graph-invariant argument that they aren't isomorphic.
- Question 26 hint: by induction, what is the maximum number of vertices that \(n-1\) edges can connect?

- Section 9.6: 2, 18.
- Question 2: Use Dijkstra's algorithm.
- Question 18 hint: no, find a counter-example.

# Questions

- Use the theorem from lecture to determine if the graphs in section 9.2 questions 21–25 are bipartite. Either draw them as bipartite or identify the odd-length cycle.
- Read section 9.5, questions 56–60. Learn another interesting example of something that doesn't seem like a graph problem, but can be handled with graph theory. Write “I promise I read the questions” as your answer.