Matchings and Allocation Problems

A matching in a bipartite graph is a set of edges with no shared vertices — each vertex is matched to at most one partner. The maximum matching problem and the allocation problem (assigning tasks to people at minimum cost) are key applications of discrete mathematics.

---

Bipartite Graphs and Matchings

A bipartite graph has two sets of vertices (e.g., workers and jobs) with edges only between the sets. A matching pairs vertices from one set with vertices from the other so that no vertex appears in more than one pair.

Term	Definition
Matching	A set of edges with no shared vertices
Maximum matching	A matching with the most edges possible
Complete matching	A matching that matches every vertex in the smaller set
Perfect matching	A matching that matches every vertex in both sets

---

Maximum Matching Algorithm (Alternating Path)

To improve a matching $M$M:

1. Find an unmatched vertex in the first set.
2. Find an alternating path: a path that alternates between edges NOT in $M$M and edges IN $M$M, ending at an unmatched vertex in the second set.
3. Swap the status of every edge on this path (matched edges become unmatched, and vice versa).
4. The matching size increases by 1.
5. Repeat until no alternating path exists.

Worked Example

Workers: {P, Q, R, S}. Jobs: {1, 2, 3, 4}.

Possible assignments (edges):

• P: jobs 1, 2
• Q: jobs 1, 3
• R: jobs 2, 4
• S: jobs 3

Initial matching: P–1, Q–3, R–2.

S is unmatched. Find an alternating path from S:

S → 3 (not in M) → Q (matched with 3) → 1 (in M) → P (matched with 1) → 2 (not in M, unmatched in jobs? No, R is matched to 2).

Try: S → 3 → Q → 1 → P → 2 → R → 4 (unmatched!).

Alternating path: S–3, Q–3 (swap), Q–1, P–1 (swap), P–2, R–2 (swap), R–4.

New matching: S–3, Q–1, P–2, R–4. All workers matched — complete matching found.

Exam Tip: Clearly write out the alternating path, showing which edges are in the current matching and which are not. Then describe the swap. The path must start and end at unmatched vertices.

---

Hall's Marriage Theorem

A complete matching from the first set to the second set exists if and only if for every subset $S$S of the first set, the number of neighbours of $S$S in the second set is at least $|S|$∣S∣:

$|N(S)| \geq |S| \quad \text{for all } S \subseteq \text{first set}$∣N(S)∣≥∣S∣for all S⊆first set

This is called Hall's condition.

---

The Assignment (Allocation) Problem