What is a matching?
A café has four jobs to fill today (baking, the till, delivery driving and serving tables) and four workers. Not everyone can do everything. Draw the workers on the left, the jobs on the right, and an edge whenever a worker is qualified for a job. This is a bipartite graph (Unit 1): every edge goes between the two sides.
Definitions
A matching is a set of edges with no two sharing a vertex: nobody is given two jobs, and no job goes to two people.
A maximum matching has as many edges as possible. A perfect matching covers every vertex.
Step through the frames to see a matching grow from 3 pairs to a perfect 4:
Swipe or scroll sideways to step through.
Who can do what
An edge means the worker is qualified for the job. Each worker takes at most one job and each job needs one worker.
A greedy matching: 3 pairs
Go down the list giving each worker their first free job: Ada–Bake, Bo (nothing left), Cy–Cash, Di–Drive. Bo and Serve (amber) are left out. Stuck?
An augmenting path
Bo → Bake → Ada → Cash → Cy → Serve. It starts and ends at unmatched vertices and alternates: unused (amber), matched (pink), unused, matched, unused.
Flip it: 4 pairs
Swap along the path: matched edges become unused and unused ones become matched. Bo gets Bake, Ada moves to Cash, Cy moves to Serve. Everyone has a job: a perfect matching.
matched pairleft out
Matchings also make sense in graphs that aren't bipartite. Pairing up 20 students as lab partners, where an edge means "willing to work together", is a matching problem on an ordinary graph. Most of this unit sticks to the bipartite case, which is the most common and has the cleanest theory.
Maximal is not maximum
The second frame shows a trap. The greedy matching (Ada–Bake, Cy–Cash, Di–Drive) is maximal: you can't add any more edges to it, because Bo's only job, Bake, is taken. But it isn't maximum: the last frame shows a matching with 4 edges.
| Word | Meaning |
|---|---|
| Maximal matching | Can't be extended by simply adding another edge. A "local" best. |
| Maximum matching | Has the largest possible number of edges. The true best. |
Every maximum matching is maximal, but not the other way round. To get from a maximal matching to a maximum one, you sometimes have to rearrange existing pairs, not just add new ones. That's exactly what augmenting paths do.
Good news
A maximal matching is never too bad: it always has at least half as many edges as a maximum matching. Each edge of the best matching shares a vertex with some edge of any maximal matching, and each edge of the maximal matching can "block" at most two edges of the best one.
Augmenting paths
Given a matching, call a vertex free if no matched edge touches it.
Definition
An augmenting path is a path that starts and ends at free vertices and whose edges alternate: not matched, matched, not matched, …, not matched.
Such a path always has one more unmatched edge than matched edges. So if you flip every edge along it (matched becomes unmatched and vice versa), the matching grows by exactly one. Everyone along the path still has at most one partner: the people in the middle just swap partners, and the two free ends each gain one.
Amazingly, augmenting paths are the only thing you ever need:
Berge's theorem (1957)
A matching is maximum if and only if there is no augmenting path.
This gives an algorithm: start with any matching (even an empty one), search for an augmenting path, flip it, and repeat until none exists. In a bipartite graph, a breadth-first search (Unit 4) that alternates between unused and matched edges finds augmenting paths efficiently. The fastest classic version, the Hopcroft–Karp algorithm (1973), handles millions of vertices.
Try it. In the greedy matching (Ada–Bake, Cy–Cash, Di–Drive), is there an augmenting path that starts at Bo and ends somewhere other than Serve?
Show answer
No. An augmenting path must end at a free job, and the only free job is Serve. From Bo the path is forced: Bo–Bake (Bo's only edge), then Bake–Ada (its matched edge), then Ada–Cash (Ada's other edge), then Cash–Cy, then Cy–Serve or Cy–Drive. Cy–Drive leads to the matched edge Drive–Di, and Di has no other jobs: a dead end. So Bo → Bake → Ada → Cash → Cy → Serve is the only augmenting path.
Hall's marriage theorem
When can every worker get a job? Sometimes it's obviously impossible:
For any group of workers S, write N(S) for the set of jobs that at least one of them can do (their "neighbourhood"). If some group is bigger than its neighbourhood, some member of that group must miss out. Philip Hall proved in 1935 that this is the only thing that can go wrong:
Hall's theorem
In a bipartite graph, every vertex on the left can be matched if and only if, for every group S of left vertices, |N(S)| ≥ |S|. In words: every group of k workers can do at least k different jobs between them.
It's called the marriage theorem because of an old way of phrasing it: if every group of k women knows at least k men between them, then every woman can marry a man she knows. The theorem turns a search problem ("find an assignment") into a checkable condition, and when the condition fails, the guilty group is proof that no assignment exists.
Example: a consequence for regular graphs
Suppose every worker can do exactly 3 jobs and every job can be done by exactly 3 workers. Then a perfect matching always exists. Take any group S of k workers: they have 3k edges between them, all landing in N(S). Each job in N(S) receives at most 3 edges, so |N(S)| ≥ 3k ÷ 3 = k. Hall's condition holds.
Try it. Five students each list the clubs they'd join. Amy: chess, drama. Ben: chess. Cat: drama. Dan: chess, drama, music. Eve: music, art. Each club can take one new student. Can every student get a club?
Show answer
No. Look at the group {Amy, Ben, Cat}: between them they only want chess and drama, 2 clubs for 3 students. Hall's condition fails. (Without Cat, it would work: Ben–chess, Amy–drama, Dan–music, Eve–art.)
König's theorem
Here's another "min = max" theorem of the kind we met in Unit 2. A vertex cover is a set of vertices that touches every edge, like a set of security cameras placed at junctions so that every corridor is watched.
Each edge of a matching needs its own cover vertex, since matched edges don't share vertices. So any vertex cover is at least as big as any matching. For bipartite graphs, Dénes Kőnig proved in 1931 that the best possible values meet exactly:
König's theorem
In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
In the café example, the maximum matching has 4 edges, so no fewer than 4 vertices can cover all the edges. And 4 is enough: the four workers touch every edge. In the Hall example, the maximum matching has 3 edges (say Ed–P, Gus–Q, Hal–R), and {P, Q, Hal} is a vertex cover of size 3. That cover is a certificate that no 4-edge matching exists.
Stable matching
So far any pairing was as good as any other. But what if everyone has preferences? Students rank schools, schools rank students. Now a new danger appears.
Definitions
In a matching, a student s and a school c form a blocking pair if they're not matched to each other but both would rather be: s prefers c to their own school, and c prefers s to one of its own students.
A matching with no blocking pairs is stable.
A blocking pair is a deal waiting to happen behind everyone's back: both sides gain by breaking their assigned matches and going off together. Unstable assignments tend to unravel. Before such systems were designed, some markets were chaotic, with offers made earlier and earlier and frequent broken commitments.
Here are three students (A, B, C) and three schools (X, Y, Z), each school with one place:
Students' preferences
| Student | 1st | 2nd | 3rd |
|---|---|---|---|
| A | X | Y | Z |
| B | X | Z | Y |
| C | Y | X | Z |
Schools' preferences
| School | 1st | 2nd | 3rd |
|---|---|---|---|
| X | B | A | C |
| Y | A | C | B |
| Z | A | B | C |
Is A–X, B–Z, C–Y stable? Check every unmatched pair. B prefers X to Z, and X prefers B to A. So B and X form a blocking pair: this matching is unstable.
The Gale–Shapley algorithm
Does a stable matching always exist? In 1962 David Gale and Lloyd Shapley proved that it does, with a method as simple as a dance:
- Every unmatched student applies to their favourite school that hasn't already rejected them.
- Each school looks at everyone currently applying, plus the student it's holding (if any). It tentatively holds the one it likes best and rejects the rest.
- Repeat until no student is rejected. Then the held offers become final.
| Round | Applications | Schools decide | Held after round |
|---|---|---|---|
| 1 | A → X, B → X, C → Y | X prefers B to A: holds B, rejects A. Y holds C. | X: B, Y: C |
| 2 | A → Y (A's 2nd choice) | Y prefers A to C: holds A, rejects C. | X: B, Y: A |
| 3 | C → X (C's 2nd choice) | X prefers B to C: rejects C. | X: B, Y: A |
| 4 | C → Z (C's 3rd choice) | Z holds C. | X: B, Y: A, Z: C |
Check stability: B has their first choice. A prefers X, but X prefers B to A. C prefers Y and X, but Y prefers A to C and X prefers B to C. No blocking pair, so the matching is stable.
Why does it always work? Students only move down their lists, and schools only trade up. Each student applies to each school at most once, so the process must end. And it ends stable: if student s prefers school c to their final school, then s applied to c earlier and was rejected (immediately or later) for someone c liked better. Since schools only trade up, c ends with someone it prefers to s. So s and c can't be a blocking pair.
Who proposes matters
The side that applies does best. With students applying, every student gets the best school they could get in any stable matching. If the schools applied instead, the schools would get their best possible stable outcome. Designers of real systems choose the applying side carefully. Many school-choice systems let students apply, partly because it then never pays a student to lie about their preferences.
Matching in the real world
- Kidney exchange. A patient may have a willing donor whose kidney isn't compatible. If patient 1's donor matches patient 2 and patient 2's donor matches patient 1, a swap saves both. Exchange programmes build a graph of compatibilities and search it for swaps and longer chains, and have arranged thousands of transplants.
- Ride-hailing. Every few seconds, waiting passengers and free drivers form a bipartite graph weighted by pick-up time, and the app chooses a matching that keeps waits short.
- Assigning tasks. Allocating exam rooms to sessions, nurses to shifts or processors to jobs are all matching problems, often with weights (the "assignment problem").
- Online ads. Ad slots are matched to advertisers as people load web pages, in real time.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. What's the largest possible matching in a graph with 11 vertices?
Show answer
Each edge uses 2 vertices, so at most ⌊11 ÷ 2⌋ = 5 edges. One vertex is always left over; no perfect matching is possible.
2. Does the cycle C6 have a perfect matching? Does C7?
Show answer
C6: yes, take every other edge. C7: no, it has an odd number of vertices.
3. How many perfect matchings does the complete bipartite graph K3,3 have?
Show answer
The first left vertex has 3 choices, the second 2, the third 1: 3 × 2 × 1 = 6.
4. A matching has 7 edges, and you find an augmenting path of length 9 (9 edges). How many edges does the matching have after flipping the path?
Show answer
The path has 5 unmatched and 4 matched edges. Flipping removes 4 and adds 5: 7 − 4 + 5 = 8 edges. An augmenting path always adds exactly one.
5. In the stable-matching example, what happens if the schools apply instead (each school to its favourite student, students holding their best offer)?
Show answer
Round 1: X → B, Y → A, Z → A. A holds Y (A prefers Y to Z) and rejects Z; B holds X. Round 2: Z → B (its 2nd choice). B prefers X to Z, so rejects Z. Round 3: Z → C. C holds Z. Result: A–Y, B–X, C–Z, the same matching. In this example it's the only stable matching, so both versions agree.
6. Use Hall's theorem to explain why, if every worker is qualified for at least k jobs and every job accepts at most k workers (counting edges), every worker can be placed.
Show answer
Take a group S of workers. They send at least k|S| edges into N(S). Each job there receives at most k edges, so |N(S)| ≥ k|S| ÷ k = |S|. Hall's condition holds for every group, so everyone can be matched.
Summary and glossary
- A matching pairs vertices along edges, with nobody paired twice. Bipartite graphs model two-sided pairing problems.
- Maximal (can't add an edge) is weaker than maximum (largest possible).
- Flipping an augmenting path grows a matching by one. A matching is maximum exactly when no augmenting path exists (Berge).
- Hall's theorem: everyone on one side can be matched exactly when every group of k has at least k neighbours.
- König's theorem: in bipartite graphs, maximum matching = minimum vertex cover.
- With preferences, the Gale–Shapley algorithm always finds a stable matching, with no blocking pairs.
- Matching
- A set of edges, no two sharing a vertex.
- Perfect matching
- A matching that covers every vertex.
- Maximal matching
- A matching that can't be extended by adding an edge.
- Maximum matching
- A matching with as many edges as possible.
- Augmenting path
- An alternating path between two free vertices; flipping it adds an edge.
- Neighbourhood N(S)
- All vertices adjacent to at least one vertex of S.
- Vertex cover
- A set of vertices touching every edge.
- Blocking pair
- Two unmatched partners who both prefer each other to their assigned matches.
- Stable matching
- A matching with no blocking pair.