CSE 321 Assignment #8
Autumn 1997

Due: Wednesday, December 10, 1997.

Reading assignment: Read the text, Discrete Mathematics and Its Applications Sections 7.1-7.5. Concentrate only on simple undirected and directed graphs.

Problems:

  1. Section 7.2, page 448, Problem 20.

  2. Section 7.2, page 448, Problem 26. (Hint: Use a proof by contradiction or the generalized pigeonhole principle.)

  3. Section 7.3, page 459, Problem 28

  4. Section 7.3, page 459-60, Problems 34, 36, 38, 40, 42, 44. Justify your answers.

  5. Section 7.4, page 470, Problem 6.

  6. Section 7.5, page 483-84, Problems 2, 4, 6.

  7. (Bonus) Show that if undirected graph G is NOT connected then its complement IS connected.

  8. (Bonus) Section 7.4, Page 470, problem 14.

  9. (Bonus) Page 524, 8 (a). (This question should look very familiar.)