Matchings in Bipartite Graphs

Recall that a bipartite graph \(\GVE\) is one in which the vertices can be properly colored using only two colors. It is clear that such a coloring then partitions \(V\) into two independent sets \(V_1\) and \(V_2\), and so all the edges are between \(V_1\) and \(V_2\). Bipartite graphs have many useful applications, particularly when we have two distinct types of objects and a relationship that makes sense only between objects of distinct types. For example, suppose that you have a set of workers and a set of jobs for the workers to do. We can consider the workers as the set \(V_1\) and the jobs as \(V_2\) and add an edge from worker \(w\in V_1\) to job \(j\in V_2\) if and only if \(w\) is qualified to do \(j\).

For example, the graph in is a bipartite graph in which we've drawn \(V_1\) on the bottom and \(V_2\) on the top.

If \(\GVE\) is a graph, a set \(M\subseteq E\) is a matching in \(\bfG\) if no two edges of \(M\) share an endpoint. If \(v\) is a vertex that is the endpoint of an edge in \(M\), we say that \(M\) saturates \(v\) or \(v\) is saturated by \(M\). When \(\bfG\) is bipartite with \(V=V_1\cup V_2\), a matching is then a way to pair vertices in \(V_1\) with vertices in \(V_2\) so that no vertex is paired with more than one other vertex. We're usually interested in finding a maximum matching, which is a matching that contains the largest number of edges possible, and in bipartite graphs we usually fix the sets \(V_1\) and \(V_2\) and seek a maximum matching from \(V_1\) to \(V_2\). In our workers and jobs example, the matching problem thus becomes trying to find an assignment of workers to jobs such that

1. each worker is assigned to a job for which he is qualified (meaning there's an edge),
2. each worker is assigned to at most one job, and
3. each job is assigned at most one worker.

As an example, in , the thick edges form a matching from \(V_1\) to \(V_2\). Suppose that you're the manager of these workers (on the bottom) and must assign them to the jobs (on the top). Are you really making the best use of your resources by only putting four of six workers to work? There are no trivial ways to improve the number of busy workers, as the two without responsibilities right now cannot do any of the jobs that are unassigned. Perhaps there's a more efficient assignment that can be made by redoing some of the assignments, however. If there is, how should you go about finding it? If there is not, how would you justify to your boss that there's no better assignment of workers to jobs?

In , we show thick edges to show the edges with flow \(1\) in the flow corresponding to our guess at a matching from .

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.