ABSTRACT
Many applications of graphs involve pairings of vertices. For example, among a set of people, some pairs are compatible as roommates. We want to know under what conditions we can pair them all up. In Chapter 1, we considered the case of jobs and applicants, askingwhether all the jobs can be competently filled. Bipartite graphs have a natural vertex partition into two sets, and we want to knowwhether the edge pair can pair up the two sets. However, the graph need not be bipartite in the roommate problem.
