Midterm 2 Study Guide

Chapters covered: 5-7

  1. Definition of Cut Vertex (section 5.1). Examples.
  2. Theorem 5.1, Corollary 5.2, Theorem 5.3.
  3. Corollary 5.4. Proof of Theorem 5.5
  4. Nonseparable graphs (section 5.2). Theorem 5.7.
  5. Blocks. Be able to explain the equivalence relation of theorem 5.8 (why it is equivalence) and what its equivalence classes are. Corollary 5.9 (no proof).
  6. Give examples of blocks of order 2, 3, 5 in a graph.
  7. Definitions of vertex-cuts, minimum vertex-cuts, vertex-connectivity, edge-cuts, minimum edge-cuts, edge-connectivity (section 5.3).
  8. Proof of Theorem 5.10, Theorem 5.11
  9. Eulerian trails/circuits/graphs (section 6.1). Examples of graphs with and without such trails/circuits.
  10. Proof of Theorem 6.1.
  11. Corollary 6.2
  12. Hamiltonian paths/cycles/graphs (section 6.2). Examples of graphs with and without such paths/cycles.
  13. Proof of Theorem 6.4.
  14. Theorem 6.5 and its consequences. Theorem 6.6.
  15. Directed graphs and related definitions (section 7.1). Theorem 7.1
  16. Weakly connected vs strongly connected. Directed distance.
  17. Theorems 7.3, 7.4, 7.5.
  18. Tournaments (section 7.2). Transitive tournaments. Theorem 7.6.
  19. Proof of Theorem 7.7
  20. Proof of Theorem 7.8
  21. Proof of Theorem 7.9
  22. Theorem 7.10

Practice problems: