Matchings

Imagine that one is tasked with assigning hotel rooms, which are all for two occupants, to n guests, but where there is a list of couples who are incompatible and cannot, for some reason, share a hotel room. Is it possible to find a solution to this problem? In terms of graphs, this is the matching problem, asking if there is a perfect matching of a given graph. In this chapter, we shall study matchings and prove Tutte’s theorem, which proves that the existence of a perfect matching is equivalent to the connected structure of its subgraphs. We will also consider stable matchings for graphs where each vertex has a preference order for its neighbours. One can think of this as the real-life situation of singles having an order preference for the others singles that they know. Given a set of singles and their preferences, one can ask if it is possible to match up the singles in couples in such a way that there is no pair, not coupled with each other, who both prefer each other to their own partner. We will investigate this problem and give an algorithm to solve this in the case of bi-partite graphs.