Discrete Math › Section C · Graph theory › Topic C.9

Matching in bipartite graphs

Workers and jobs, volunteers and shifts, applicants and places: many problems ask whether each member of one group can be paired with a different acceptable member of another. Hall's theorem gives an exact test, and augmenting paths show how to build the pairing.

Pairing two groups

Four volunteers must each cover a different shift at a food bank, and each has said which shifts they can do. Draw the volunteers on one side, the shifts on the other, and an edge for each workable pairing. The graph is bipartite, with sides \(A\) (volunteers) and \(B\) (shifts), because every edge joins a volunteer to a shift. The question is now about the graph: can we choose edges so that every volunteer gets exactly one shift and no shift is given twice? The same model fits workers and jobs, taxis and riders, or committees and the people who chair them.

Matchings

A matching is a set of edges, no two of which share a vertex. A vertex touched by one of its edges is matched; the others are unmatched. A matching of \(A\), sometimes called a complete matching from \(A\), matches every vertex of \(A\). When both sides are matched completely, which needs \(|A| = |B|\), the matching is perfect. A maximum matching has the largest possible number of edges. A maximal matching only means that no further edge can be added as things stand, which is weaker. On the path a-b-c-d, the single edge bc is maximal, but the maximum matching is {ab, cd}, with two edges.

What can go wrong

Every failure has the same cause: a crowd squeezed into too little room. A volunteer with an empty list is a crowd of one with no room at all; if five volunteers can, between them, do only four shifts, one of the five is left out however the shifts are handed round. To make this precise, write \(N(S)\) for the set of vertices in \(B\) adjacent to at least one vertex of a set \(S \subseteq A\). If some \(S\) has \(|N(S)| < |S|\), the vertices of \(S\) are competing for too few partners, and no matching of \(A\) exists. The condition \(|N(S)| \ge |S|\) for every \(S\) is called Hall's condition.

Hall's theorem

Hall's condition is obviously necessary. The surprise is that it is also sufficient. Hall's theorem, proved by Philip Hall in 1935, states that a bipartite graph with sides \(A\) and \(B\) has a matching of \(A\) if and only if

|N(S)| \ge |S| \text{ for every } S \subseteq A

It is sometimes called the marriage theorem, after an older way of stating the problem. To show a matching does not exist, you need only one set \(S\) that breaks the condition. To show one does exist, it is usually easier to construct it than to check all \(2^{|A|}\) subsets.

Worked example: finding the obstacle

Volunteers Ann, Bo, Cy and Di can do these shifts: Ann 1 or 2; Bo only 1; Cy 1 or 2; Di 2, 3 or 4. 1. Try to match everyone: Bo must take 1, so Ann and Cy must share shift 2. Something is wrong. 2. Name the obstacle: take \(S = \{\text{Ann, Bo, Cy}\}\). Their possible shifts are \(N(S) = \{1, 2\}\). 3. Since \(|N(S)| = 2 < 3 = |S|\), Hall's condition fails and no matching of all four volunteers exists. 4. The best possible is a matching of size 3, such as Bo-1, Ann-2, Di-3. Adding shift 3 to Cy's list would fix the problem: Cy-3, Di-4.

Alternating and augmenting paths

Given a matching \(M\), an alternating path is a path whose edges alternate between edges not in \(M\) and edges in \(M\). An augmenting path is an alternating path that starts and ends at unmatched vertices, so its first and last edges are not in \(M\). It has one more edge outside \(M\) than inside. Swapping along it, taking out its \(M\)-edges and putting in its other edges, gives a new matching with exactly one more edge. Berge's theorem says a matching is maximum if and only if no augmenting path exists, so searching for augmenting paths is a complete method.

Worked example: growing a matching

Sides \(\{p, q, r\}\) and \(\{1, 2, 3\}\), with edges p1, p2, q1, r2 and r3. Start with \(M = \{p1, r2\}\). 1. Unmatched vertices: q and 3. Vertex q's only edge, q1, leads to a matched vertex, so a simple greedy step is stuck. 2. Build an alternating path from q: q-1 (not in \(M\)), 1-p (in \(M\)), p-2 (not), 2-r (in \(M\)), r-3 (not). It ends at the unmatched vertex 3, so it is augmenting. 3. Swap: remove p1 and r2, add q1, p2 and r3. 4. The new matching \(\{q1, p2, r3\}\) has 3 edges, one more than before, and covers every vertex: it is perfect.

Worked example: when everyone has equal choice

Suppose every vertex on both sides has the same degree \(k \ge 1\); for instance, each of 6 workers is qualified for exactly 2 jobs, and each of 6 jobs has exactly 2 qualified workers. Claim: a perfect matching exists. 1. Take any \(S \subseteq A\). Exactly \(k|S|\) edges leave \(S\). 2. All of them end in \(N(S)\), and each vertex of \(N(S)\) receives at most \(k\) edges in total, so \(k|N(S)| \ge k|S|\). 3. Dividing by \(k\) gives \(|N(S)| \ge |S|\): Hall's condition holds. 4. So \(A\) can be matched, and since counting edges gives \(k|A| = k|B|\), the sides are equal and the matching is perfect.

Matching in practice

Repeatedly searching for augmenting paths finds a maximum matching efficiently, and the Hopcroft-Karp algorithm does this quickly even for large graphs. König's theorem adds a neat certificate: in a bipartite graph, the size of a maximum matching equals the smallest number of vertices that together touch every edge. When edges carry costs, the Hungarian algorithm finds a perfect matching of least total cost, as in assigning drivers to deliveries. Matching students to schools or doctors to hospitals adds rankings and is a different problem, stable matching, solved by the Gale-Shapley algorithm.

Common mistakes to avoid

First, checking Hall's condition only for single vertices; a matching can fail even when every vertex has degree at least 1, because a group can be deficient. Second, believing a maximal matching must be maximum: a stuck greedy matching can often still be improved by an augmenting path. Third, starting or ending an augmenting path at a matched vertex. Fourth, expecting a perfect matching when the sides have different sizes; at best, the smaller side can be matched.

Key takeaways

A matching is a set of edges with no shared vertices; a matching of \(A\) covers every vertex of \(A\), and a perfect matching covers both sides. Hall's theorem: a bipartite graph has a matching of \(A\) if and only if \(|N(S)| \ge |S|\) for every \(S \subseteq A\), so one deficient set proves that none exists. Augmenting paths enlarge a matching by one edge, and a matching is maximum exactly when none remains. A bipartite graph in which every vertex has the same positive degree has a perfect matching.

Flashcards

Flashcard

Matching

A set of edges with no two sharing a vertex

Each vertex is used at most once.

Test your understanding

Question 1 of 5

A bipartite graph has sides {p, q, r} and {1, 2, 3} and edges p1, p2, q1, r2, r3. Which set of edges is a matching?

Question 2 of 5

Workers X, Y, Z, W are qualified for these jobs: X for a; Y for a or b; Z for a or b; W for b, c or d. Which set S of workers breaks Hall's condition?

Question 3 of 5

A matching has 4 edges, and you find an augmenting path containing 7 edges. After swapping along it, how many edges does the matching have?

Question 4 of 5

Six workers are each qualified for exactly 2 of 6 jobs, and each job has exactly 2 qualified workers. What can you conclude?

Question 5 of 5

A matching in a bipartite graph has no augmenting path. What does Berge's theorem let you conclude?

← Previous topicNext topic →