# Homework #12

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

1. 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.
2. 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.