Midterm 3 Study Guide

Chapters covered: 8.1, 9.1, 10.2 (And review of previous chapters, exam is somewhat cummulative)

  1. Definition of a matching, and an independent set of edges. Examples of bipartite graphs with and without maximum sized matchings.
  2. Hall’s condition. Theorem 8.3 with its proof.
  3. Restatement of theorem 8.3 as theorem 8.4 and theorem 8.5.
  4. Theorem 8.6
  5. edge/vertex independence numbers and edge/vertex covering numbers definitions.
  6. When is a graph called planar? What are the regions for such a graph, and what is the boundary of such a region?
  7. Theorem 9.1 (Euler’s identity) with its proof.
  8. Theorem 9.2 with its proof.
  9. Corollary 9.3 and 9.4. Proof of corollary 9.4.
  10. Theorem 9.5 with its proof.
  11. Theorem 9.7.
  12. Show that the Petersen graph is not planar, by showing it has a subdivision of \(K_{3,3}\).
  13. Explain how map-coloring is related to vertex-coloring in a graph.
  14. What is the chromatic number of a graph? Theorem 10.1.
  15. Theorem 10.2
  16. A graph has chromatic number at most \(k\) if and only if its vertex set can be broken in \(k\) disjoint independent sets. (bottom of page 269)
  17. Definition of clique number. Theorem 10.5 with proof.
  18. Theorem 10.7, 10.9.
  19. The shadow graph, theorem 10.10 with sketch of its proof.

Practice problems: