A bipartite graph splits its nodes into two sides — call them left and right — with every edge running from one side to the other, never within a side. A matching is a set of edges that share no endpoint: no left node appears twice, no right node appears twice. Think workers and jobs, where an edge means "this worker is qualified for this job" — a matching is a valid one-to-one assignment, and the maximum matching is the largest number of workers you can place at once. This is a fourth question about graphs the site now covers, and unlike Minimum Spanning Trees or Shortest Paths it isn't obviously related to Maximum Flow at first glance — there's no capacity, no source, no sink anywhere in the problem statement. The connection turns out to be exact, not approximate: build one small flow network from the matching problem, and Edmonds-Karp's own algorithm — unmodified — finds the maximum matching as a side effect of finding the max flow.
The construction: add a new source node S with a capacity-1 edge to every
left node, a new sink node T with a capacity-1 edge from every right node, and
keep every original left-to-right edge at capacity 1. Every unit of flow from S to
T now has to pass through exactly one left node and exactly one right node — and because each of
those nodes has only one unit of capacity feeding it, no node can carry two units at once. That's precisely
what a matching forbids. See Why below for the argument that the max flow in this network is always exactly
the size of the maximum matching, not just an upper or lower bound on it.
Three left nodes (L1–L3), three right nodes (R1–R3), source S and sink T wired in as just described. Press Step or Run to repeatedly find the shortest S→T augmenting path (identical Edmonds-Karp BFS rule as the Maximum Flow page) and push one unit along it. The first two paths are the obvious kind — an unmatched left node reaches straight through to an unmatched right node. Watch the third: it's longer, and it runs backward through an already-matched edge before finding a new right node — that reverse hop un-matches one pair to free up a better overall matching, the same "residual edge undoes a choice" idea the Maximum Flow page introduced, now with a very concrete meaning: it's exactly what matching theory calls an alternating path.
Two directions to the argument. First, any matching gives a valid flow of the same size: send one unit
S→l, l→r, r→T for every matched pair (l, r) — no node is
reused across pairs (that's what "matching" means), so no capacity is ever exceeded. So the max flow is at
least the max matching size. Second, every integer flow in this network decomposes into unit paths
of the form S→l→r→T — no other shape is possible, since every node other than S
and T has exactly one unit of capacity in and one unit out. Because every edge has capacity 1
and 1 is an integer, Edmonds-Karp's own bottleneck arithmetic guarantees the flow it finds is integral (a
bottleneck computed from all-integer capacities is always an integer, and every augmentation adds an integer
amount) — so the max flow decomposes cleanly into whole l→r pairs, each node appearing in at
most one path since its single unit of capacity is already spent after the first. That decomposition
is a matching, exactly the same size as the flow. Both directions together: max flow equals maximum
matching, always, for this specific construction.
The "long path un-matches something" behavior the demo shows is the flow-network mirror of what matching theory calls Kuhn's algorithm (also taught as part of the Hungarian method): search for an alternating path — unmatched edge, matched edge, unmatched edge, ... — starting and ending at unmatched nodes. Flipping every edge on it (matched ↔ unmatched) grows the matching by exactly one. That's described purely in matching terms, with no explicit source, sink, or capacity anywhere — but it's the same search, edge for edge, as an Edmonds-Karp augmenting path in this reduction: the reverse residual hop through an already-matched edge is precisely "the matched edge in the alternating path," and every forward hop through an unmatched edge is precisely "the unmatched edge in the alternating path." This page builds the explicit flow network and reuses Edmonds-Karp verbatim rather than implementing Kuhn's algorithm directly, to make the connection to the rest of this site's Network Flow content concrete — the two are the same algorithm wearing different vocabulary, not two different algorithms that happen to agree.
Builds the flow network from a plain edge list, then runs the exact same BFS-augmenting-path loop as Maximum Flow's reference implementation:
function bipartiteMatching(leftCount, rightCount, edges) {
// edges: [[leftIndex, rightIndex], ...], both 0-based
const S = 0, T = leftCount + rightCount + 1, N = T + 1;
const cap = Array.from({ length: N }, () => new Array(N).fill(0));
for (let l = 1; l <= leftCount; l++) cap[S][l] = 1;
for (let r = 1; r <= rightCount; r++) cap[leftCount + r][T] = 1;
edges.forEach(([l, r]) => { cap[l + 1][leftCount + r + 1] = 1; });
const flow = Array.from({ length: N }, () => new Array(N).fill(0));
let matchSize = 0;
while (true) {
const parent = new Array(N).fill(-1);
parent[S] = S;
const queue = [S];
while (queue.length && parent[T] === -1) {
const u = queue.shift();
for (let v = 0; v < N; v++) {
if (cap[u][v] - flow[u][v] > 0 && parent[v] === -1) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[T] === -1) break; // no augmenting path — matching is maximum
for (let v = T; v !== S; v = parent[v]) {
flow[parent[v]][v] += 1;
flow[v][parent[v]] -= 1; // opens the reverse edge — an alternating-path un-match
}
matchSize++;
}
const pairs = [];
for (let l = 1; l <= leftCount; l++) {
for (let r = 1; r <= rightCount; r++) {
if (flow[l][leftCount + r] > 0) pairs.push([l - 1, r - 1]);
}
}
return { size: matchSize, pairs };
}Checked against a brute-force matcher (try every subset of edges, keep the largest conflict-free one) across 2,000 randomly generated bipartite graphs of up to 5 left and 5 right nodes each, at several edge densities — zero mismatches, and every returned pairing independently confirmed to touch each node at most once.
Matching greedily — first-available edge, never undone — gets stuck below the true maximum. On this page's own graph, a greedy pass finds L1–R1 and L3–R2 immediately, then has nothing left to offer L2 (its only neighbor, R1, is already taken) — greedy stops at a matching of size 2. The true maximum is 3: L1–R2, L2–R1, L3–R3, reachable only by first un-matching L1 from R1 (and L3 from R2) to make room. This is the exact same shape of failure the Maximum Flow page demonstrated with a 2,000-augmentation blowup — a locally reasonable first choice can block a better global combination — except here it isn't just slower, it's permanently wrong: a greedy matcher that never revisits a decision has no way to discover the fix on its own, however long it runs.
Reverse residual edges are what make revisiting a decision possible — verified by removing them. A forward-only version of this same algorithm (BFS restricted to original left→right edges, no reverse hop through an already-matched edge) was run against this page's exact graph: it finds the same first two paths, then has nowhere to go — final matching size 2, permanently short of the true maximum of 3, matching greedy's own failure above exactly. This is the Maximum Flow page's "reverse edges aren't an optimization, they're required for correctness" pitfall again, but concrete in matching terms: without the reverse hop, there is no way to express "un-match this pair," and Kuhn's alternating-path algorithm has no alternating paths to find.
This reduction only handles the unweighted, one-sided question "how many pairs." If edges instead carried a cost or value and the goal were the cheapest (or highest-value) valid assignment rather than the largest one — the classic assignment problem — this exact construction doesn't answer it: max flow only ever counts units, it has no notion of an edge being preferable to another edge of the same capacity. That needs a different algorithm — the Hungarian Algorithm solves weighted bipartite matching directly, via row/column potentials rather than a flow network, and is not the same problem as what's demonstrated here.
The reduction leans on the graph being bipartite — it doesn't generalize to matching in an arbitrary graph. A general (non-bipartite) graph can have odd-length alternating cycles that this two-sided source/sink construction has no way to represent — there's no consistent way to label one "side" of an odd cycle as always-left or always-right. Maximum matching in a general graph is a real, well-studied problem (Edmonds' Blossom algorithm), but it needs machinery this flow-network reduction doesn't have, not an extension of it — a genuinely different algorithm, out of scope here.
Time: O(E · min(|L|, |R|)) — sharper than the general Edmonds-Karp bound of
O(VE) from the Maximum Flow page, because every
source and sink edge here has capacity exactly 1: the max flow (and so the number of augmentations, one unit
each) can never exceed the smaller side's node count, regardless of how many edges connect them. Each BFS
costs O(E) (O(V²) as implemented here with a dense capacity matrix, fine for six
nodes), for a total of O(E) · O(min(|L|, |R|)). Space: O(V²) for
the dense capacity/flow matrices as implemented, or O(V + E) with adjacency lists.
This page's Edmonds-Karp reduction is the simplest correct route to a maximum bipartite matching, not the
fastest — it needed three separate augmenting-path searches to match this page's own demo graph.
Hopcroft-Karp finds two of those same three edges in a
single pass instead of three separate ones, reaching O(E√V) by batching every shortest
augmenting path into one phase rather than stopping at the first.
See Choosing a Network Flow Algorithm for how this reduction compares against the site's other ten Network Flow entries — including Hungarian Algorithm, for when the pairing needs to be cheapest, not just largest.