Bipartite Matching

Build one-to-one pairings, preview alternating reassignment paths and distinguish a maximum matching from a maximal or perfect one.

Can an earlier pair move?

Two applicants can both accept the same job, but assigning that job twice is not a matching. A bipartite graph separates the two kinds of objects into left and right sets. An edge means compatibility, and a matching selects edges that never share a vertex. The objective here is to make as many pairs as possible. Sometimes this requires moving an earlier assignment, rather than leaving every previous decision fixed.

One partner per vertex

Write the graph as G = (L, R, E), where L and R are disjoint sets and every edge joins one member of each. A matching M is a subset of E in which every vertex occurs at most once. Its cardinality |M| is the number of pairs. A maximum matching has the largest possible cardinality. A perfect matching covers every vertex on both sides, so the two sides must have equal size. Covering just the smaller side is not enough to call a matching perfect.

|M| ≤ min(|L|, |R|)
Perfect: |M| = |L| = |R|

The explorer labels the two sides separately: L0 and R0 are different vertices. Consequently the input pair 0 0 is a legal cross-partition edge, not a self-loop. Compatibility edges have no intrinsic direction. The arrows shown on a candidate path describe the search, rather than changing the graph into a directed matching problem.

A greedy pair that needs reassignment

Take L = {L0, L1} and R = {R0, R1}, with edges L0–R0, L0–R1 and L1–R0. Selecting L0–R0 first leaves no edge directly joining the two remaining free vertices. This size-one matching is maximal: no single edge can simply be added. It is not maximum. Reassign L0 to R1 and give R0 to L1. The resulting two pairs hit the upper bound min(2, 2), proving optimality without trusting the implementation.

Replay step	Event	Committed matching	Size
0	Initial	None	0
1	Preview L0 → R0	None	0
2	Apply first path	L0–R0	1
3	Preview L1 → R0 → L0 → R1	L0–R0	1
4	Apply reassignment	L0–R1, L1–R0	2
5	No augmenting path	L0–R1, L1–R0	2

The second candidate alternates between an unused edge L1–R0, a currently used edge R0–L0 and another unused edge L0–R1. Remove the one used edge and add the other two: the net change is 2 − 1 = 1 pair. Its endpoints were free, and each interior vertex exchanges one partner for another, so the result remains a matching. A preview changes no committed pair; only its following apply step performs this exchange.

Why alternating paths certify the answer

An augmenting path begins at a free vertex, ends at another free vertex, and alternates between unused and used edges. Flipping membership along it is the symmetric difference M △ P. There is one more unused edge than used edge, so its cardinality increases by one. Berge’s characterization states that a matching is maximum exactly when it has no augmenting path. A matching with no immediately addable edge may still have a longer augmenting path, which is why maximal and maximum are different claims.

This explorer repeatedly runs one multi-source breadth-first search. All free left vertices enter the queue in ascending index order. At a left vertex, unused edges are examined in ascending right-index order; at a matched right vertex, the search follows its unique partner back to the left. The search returns as soon as it discovers a free right vertex. This fixed rule makes the replay reproducible. It does not imply that a maximum matching is unique or that the chosen assignment is fair or preferable.

If the final size is a, at most a successful searches and one unsuccessful search are needed, where a ≤ min(|L|, |R|). With adjacency lists, these searches take O((a + 1)(|V| + |E|)) time. This describes the search core; preparing sorted inputs, copying replay snapshots and drawing the graph add work. The module is not Hopcroft–Karp, which uses multiple shortest augmenting paths in a phase.

Reproduce the exchange, then remove an option

Open the Bipartite Matching explorer. These steps use its actual controls. The upper result bar distinguishes the matching currently committed in the replay from the already computed maximum size.

Choose Greedy trap in Preset. Left count and Right count are both 2, and Edges contains the three pairs from the worked example. Current is 0; Maximum is 2.
Move Replay step to 1. The candidate path is L0 → R0, but Current remains 0. Press Next step to commit that pair at step 2.
Press Next step again. At step 3, follow the amber additions and dashed red removal along L1 → R0 → L0 → R1. The path panel shows three edges, two additions and one removal; Current is still 1.
Advance to step 4 to commit the exchange. Then press Show maximum to reach step 5. The two pairs are L0–R1 and L1–R0, both free counts are zero, and Perfect is Yes.
Choose R0 in Inspect vertex, or click its node. Its partner is L1. Drag the graph background or use its arrow keys to pan; Home or Reset view restores only the view.
Replace Edges with two lines, 0 0 and 1 0. The edited experiment restarts at step 0 and clears inspection. Maximum is now 1, because both left vertices compete for the only usable right vertex. Show maximum to inspect the chosen pair.
Choose Rectangular. At its maximum, both left vertices are paired, but one of the three right vertices is free. Perfect is No.
Enter 7 in Left count. An error replaces the previous results and drawing. Press Reset experiment to recover the default graph, initial replay, inspection and view.

What this matching does and does not mean

The model is a simple, unweighted bipartite graph with its two partitions supplied. It maximizes a count, not total value, preference satisfaction or stability. A real allocation system may also need capacities, fairness, costs or priorities that this model does not express. Those are different optimization problems.

Counts are whole numbers from 0 to 6. Each edge row gives a left index and a right index separated by spaces. Repeated rows describe the same edge. Invalid or out-of-range input is preserved for correction instead of being silently clamped.
With no edges the maximum size is zero, even when both sets contain vertices. With both sets empty the empty matching is perfect: there is no vertex left uncovered. If only one side is empty, the other side remains uncovered.
Different maximum matchings can exist. For example, the complete 2-by-3 graph has six maximum assignments. The displayed index order chooses one reproducibly; it is not an additional optimality criterion.
A green edge is currently committed, rather than a promise that it will never move. Amber and dashed red describe a candidate exchange. At the final step no candidate remains.
The graph is a diagram, so screen distances do not encode edge weights. Node clicks inspect identities; background gestures pan rather than modifying the graph. Large tables and long descriptions scroll inside their panels.

Read the definitions and the optimality argument

These university materials support the definitions and augmenting-path reasoning. The small graphs, numerical counts and control experiment above were worked out independently for this explorer; they are not examples attributed to these sources.

Cornell CS 6820, lecture notes on matchings, sections 1.1–1.3: pages 1–3 define matchings, prove the gain of one and the no-augmenting-path criterion, and describe the directed auxiliary graph searched by BFS or DFS.
Cornell CS 2110, Discussion 11: Using DFS for Bipartite Matching: explains one-to-one compatibility, alternating paths and reassignment by flipping their edges. This explorer chooses BFS for its deterministic search order.

Bipartite Matching