Suppose a small company has four applicants and four jobs. Each applicant is qualified for some of the jobs, not all of them. Can you hand out the jobs so that every applicant gets exactly one job they are qualified for, and no job goes to two people? That single, deceptively practical question — assign everyone at once, with no clashes — is the whole of this page.

Draw applicants as dots on the left and jobs as dots on the right, and connect an applicant to a job when they are qualified for it. This is a bipartite graph: its vertices split into two sides, and every edge crosses from left to right. A valid assignment is a special set of edges, and it has a name.

What a matching is

A matching is a set of edges, no two of which share a vertex. Picture it as pairing up: each edge you pick "uses up" both of its endpoints, so once an applicant is matched to a job, neither of them can appear in any other chosen edge. A vertex that an edge of the matching touches is saturated (matched); one left over is unmatched.

• A maximum matching is one with as many edges as possible — you cannot pair up any more.
• A perfect matching saturates every vertex: nobody is left over. On a bipartite graph with n vertices on each side, a perfect matching is exactly n edges.

Often we only care about one side. A matching saturates X if every vertex of the left set X is matched — every applicant gets a job, even if a job or two goes spare.

See one

On the left are three applicants x_1, x_2, x_3; on the right three jobs y_1, y_2, y_3. The thin grey edges are who-can-do-what. Step forward to watch a matching light up — a thick coloured set of edges in which every left dot and every right dot is touched exactly once.

The highlighted edges are x_1y_2, x_2y_1 and x_3y_3. No two touch the same dot, and all six dots are covered — a perfect matching. Notice a matching is not simply "grab any three edges": the no-shared-vertex rule is the whole difficulty.

Hall's marriage theorem

When can we guarantee that everyone on the left gets matched? The delightful answer, found by Philip Hall in 1935, is a condition you can state in one line. Think of the left side as people and the right side as potential partners: an edge means "these two would be happy together". We want to marry everyone off — hence the nickname.

For a set S of left vertices, write N(S) for its neighbourhood: every right vertex joined to at least one member of S. If a group of k people between them know only k-1 possible partners, someone must be left out — there simply aren't enough partners to go round. Hall's theorem says that this obvious obstruction is the only one.

A case that fails

Hall's condition is easy to violate. Here two applicants, x_2 and x_3, are both qualified for only one job, y_3. Take S = \{x_2, x_3\}: then |S| = 2 but N(S) = \{y_3\}, so |N(S)| = 1 < 2. Two people, one shared job — one of them is doomed to go unmatched, no matter how you shuffle everyone else.

This is the pattern to hunt for: a group on the left whose combined list of options is smaller than the group itself. Find one such starved subset and you have proved no full matching can exist — a single counterexample settles it.

How you actually find a matching: augmenting paths

Hall's theorem tells you whether a matching exists; it does not hand you one. The algorithm that does is built on augmenting paths. Start with any matching (even the empty one). An augmenting path starts at an unmatched left vertex and zig-zags unmatched, matched, unmatched, … edges, ending at an unmatched right vertex.

The trick: flip every edge along that path — matched edges become unmatched and vice-versa. The path has one more unmatched edge than matched, so flipping grows the matching by exactly one. Keep finding augmenting paths until none remains; Berge's theorem promises that when you get stuck, your matching is maximum. This is the engine inside the classic Hopcroft–Karp assignment algorithm.