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.