Outline

• Graph matchings
  matching in graphs and in bipartite graphs, optimization, stable marriage
• Perfect matchings
  perfect matchings, Hall's theorem, Tutte's condition, factors in graphs, factorizations
• Packings, coverings
  vertex covers, packings in graphs (vertex-disjoint, edge-disjoint), related coverings
• Counting objects
  counting objects in graphs, e.g. spanning trees, Cayley's formula

Goals

The topic of matchings in graphs belongs to traditional and old (since the 19th century, see Petersen) areas of pure Graph theory, and it nicely applies the findings about flow networks from Lecture 4 as well. Students should learn the classical characterizations of bipartite and general perfect matchings (Hall's and Tutte's conditions), the role of graph factorization (e.g., in tournament scheduling), and the beautiful Cayley's formula for counting spanning trees.  

Advanced course book [Graph theory (by Reinhard Diestel)

Study Chapter 2 (including the easier proofs).

This is the basic study source for Lecture 5.

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)

This book does not cover matchings and packing at all, but it devotes whole Chapter 8 (The number of spanning trees) to counting of spanning trees and Cayley's formula. It is a very inspiring reading for anybody seriously interested in mathematics.