Part IV: Matchings

This part of the book talks about the matching problem: pairing up the adjacent vertices in a graph.

Chapter 13 will introduce you to this problem. Here, you will also find out about bipartite graphs, which is mostly the setting where we will be looking for matchings. There are two reasons for this: most applications of matchings occur in bipartite graphs, and matchings are easier to find when we are looking in a bipartite graph.

There are two big (and nearly equivalent) theorems about matchings in bipartite graphs: Kőnig’s theorem and Hall’s theorem. Chapter 14 focuses on Kőnig’s theorem and Chapter 15 focuses on Hall’s theorem, but there is a thematic division between the two chapters as well. We will give Kőnig’s theorem an algorithmic proof, and so by the end of Chapter 14, you will know how to find a matching in any given bipartite graph. In Chapter 15, we will use Hall’s theorem to prove more theoretical results, guaranteeing the existence of perfect matchings in families of graphs.

In Chapter 16, we will finally look at what happens when the graph is not bipartite. The answer is: life gets much harder. We will prove Tutte’s theorem, a condition for the existence of general graphs, but we will not go much further. Instead, we will continue by looking at factorizations: decompositions of a graph into many disjoint perfect matchings.