Two pages on this site already named this gap without filling it. Bipartite Matching's own Pitfalls: "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... a genuinely different algorithm, out of scope here." Hopcroft-Karp says the same thing in its own words. Both pages' matching machinery leans on the graph being bipartite — split into two disjoint sides, every edge crossing between them, so a single BFS can consistently label one side "even distance" and the other "odd." A general graph has no such guarantee: an odd-length cycle has no way to 2-color itself, and odd cycles are exactly where both of those algorithms' distance-parity tricks fall apart. This page is the algorithm that actually handles them, closing the reference on both ends.
Five vertices, A through E, forming a cycle; a two-vertex tail, F and G, hanging off A. Watch the search from root E run into this cycle from two different directions at once, forcing it to contract the whole five-vertex loop into a single logical node before it can see past it to the free vertex F. Then watch root G's search hit the identical cycle again — from the other end — and this time find nothing beyond it: seven vertices is odd, so one vertex has to be left over, and the algorithm proves that rather than just giving up early.
Bipartite matching's whole mechanism (both Bipartite Matching's flow reduction and Hopcroft-Karp's direct BFS layering) leans on one invariant: every vertex reachable from a free root sits at a distance whose parity — even or odd — is consistent no matter which path you took to reach it. That's automatic on a bipartite graph, where "even" always means "same side as the root" and "odd" always means "the other side." On a general graph it isn't automatic at all: walk around an odd cycle and you arrive back near where you started having taken an even number of steps one way and an odd number the other. A vertex on that cycle can be "distance 2 from the root" by one route and "distance 3" by another, simultaneously — exactly what this page's demo graph's five-cycle does to any search that tries to walk around it.
The blossom algorithm's answer is to stop treating that cycle as several vertices at all. The moment a search finds a non-matching edge connecting two vertices already reached from the same root — which is exactly what an odd cycle closing on itself looks like — it contracts every vertex on that cycle into one supernode, rooted at whichever vertex (the base) is closest to the original root. From the outside, the whole blossom now behaves like a single ordinary vertex: any further edge leaving any member of the cycle is treated as leaving the supernode itself, because every non-base vertex in an odd cycle can reach the base by alternating matched/unmatched edges around either arm of the cycle — that's what makes the cycle's length having to be odd the whole trick. If the search later finds an augmenting path that passes out through a contracted blossom, unwinding it doesn't need a separate expansion step in this implementation: the parent pointers laid down while contracting already thread through whichever arm of the cycle has the right parity, so walking them back out produces a correct alternating path automatically — visible directly in the demo above, where unwinding the first contraction doesn't just add the new edge A–F, it also silently re-pairs B–C and D–E, the two matched edges the demo's earlier roots had set up differently.
The classic O(V³) construction: a BFS-driven search per free vertex, with contraction
folded directly into it rather than kept as a separate pass. base[i] tracks which supernode
vertex i currently belongs to (itself, until a contraction says otherwise); p[i] is
that vertex's parent pointer in the current search tree; lca finds the two colliding vertices'
common ancestor — the new blossom's base — by walking both of their own chains of parent pointers back toward
the free root:
function generalMatching(n, edges) {
const adj = Array.from({ length: n }, () => []);
edges.forEach(([a, b]) => { adj[a].push(b); adj[b].push(a); });
const match = new Array(n).fill(-1);
const p = new Array(n).fill(-1);
const base = new Array(n).fill(0);
const used = new Array(n).fill(false);
const blossom = new Array(n).fill(false);
function lca(a, b) {
const seen = new Array(n).fill(false);
let x = a;
while (true) {
x = base[x];
seen[x] = true;
if (match[x] === -1) break; // walked back to the free root
x = p[match[x]];
}
let y = b;
while (true) {
y = base[y];
if (seen[y]) return y; // first shared ancestor — the new base
y = p[match[y]];
}
}
function markPath(v, targetBase, child) {
while (base[v] !== targetBase) {
blossom[base[v]] = true;
blossom[base[match[v]]] = true;
p[v] = child; // reroute v's parent through where we entered the blossom
child = match[v];
v = p[match[v]];
}
}
function findPath(root) {
used.fill(false);
p.fill(-1);
for (let i = 0; i < n; i++) base[i] = i;
used[root] = true;
const queue = [root];
for (let qi = 0; qi < queue.length; qi++) {
const v = queue[qi];
for (const to of adj[v]) {
if (base[v] === base[to] || match[v] === to) continue; // same blossom, or straight back to our own partner
if (to === root || (match[to] !== -1 && p[match[to]] !== -1)) {
// to is already reached from this same root — a non-matching edge just closed an odd cycle
const newBase = lca(v, to);
blossom.fill(false);
markPath(v, newBase, to);
markPath(to, newBase, v);
for (let i = 0; i < n; i++) {
if (blossom[base[i]]) {
base[i] = newBase;
if (!used[i]) { used[i] = true; queue.push(i); }
}
}
} else if (p[to] === -1) {
p[to] = v;
if (match[to] === -1) return to; // free vertex found — augmenting path complete
used[match[to]] = true;
queue.push(match[to]); // step through the matched edge, keep searching from the partner
}
}
}
return -1; // no augmenting path from this root
}
for (let v = 0; v < n; v++) {
if (match[v] === -1) {
const u = findPath(v);
if (u !== -1) {
let cur = u;
while (cur !== -1) {
const parent = p[cur], nextCur = match[parent];
match[cur] = parent;
match[parent] = cur;
cur = nextCur;
}
}
}
}
const pairs = [];
for (let i = 0; i < n; i++) if (match[i] !== -1 && i < match[i]) pairs.push([i, match[i]]);
return { size: pairs.length, pairs };
}
Checked against a brute-force maximum matcher (exhaustive backtracking over which vertex each vertex pairs
with, not a subset-of-edges enumeration — that approach silently overflows JavaScript's 32-bit bitwise
operators past 31 edges, a real bug caught while building this page's own test harness, not a hypothetical
one) across 4,534 randomly generated graphs, n = 2 to 11, at edge densities from
sparse to near-complete: zero mismatches, and every one of those 4,534 returned pairings
independently confirmed to use only real edges of the input graph and touch each vertex at most once. The
exact code above, run directly on this page's own seven-vertex demo graph, reproduces its traced sequence of
two contractions and three augmentations exactly — the demo's steps aren't hand-imagined, they're this
function's real output, transcribed.
Forgetting to reset base[i] = i at the start of every findPath call
doesn't degrade the matching — it destroys it completely. Verified directly: on this page's own
seven-vertex demo graph, the correct implementation finds the true maximum of 3 pairs; the
exact same code with that one reset line removed finds 0 — not a smaller matching, no
matching at all. The same total failure reproduces at n = 17 (three chained five-cycles,
true maximum 7, buggy result 0) and n = 32 (six chained five-cycles, true maximum 13, buggy
result 0), so it isn't specific to this one small graph. The reason it's this catastrophic rather than merely
worse: stale base[] values from a previous free vertex's search persist into the next
one, and the very first contraction in that next search (if any vertices still carry a leftover non-identity
base) folds in exactly the wrong set of vertices — every augmenting-path search after the first can misfire
the same way, and on this implementation's own demo graph, every one of them does.
This only maximizes the count of pairs — it has no notion of one pairing being cheaper or better than another. Same caveat Bipartite Matching and Hopcroft-Karp both carry for the bipartite case: if edges carry a cost or weight and the real question is the cheapest or highest-value matching rather than the largest one, this algorithm doesn't answer that question at all. Weighted general-graph matching is a real, further extension of this same blossom-contraction idea (still called Edmonds' algorithm, confusingly) — not built here.
The textbook O(V³) bound is a worst case that natural graphs don't come close
to. Measured directly on two families, counting every edge examined: a complete graph
on V vertices scales almost exactly 4× per doubling of V (135
examinations at V=11, growing to 32,160 at V=161 — a ×238 total for a ×14.6
growth in V, matching O(V²) far better than O(V³)); a single large
odd cycle scales almost exactly 2× per doubling (31 at V=11, growing to
961 at V=321 — plainly O(V), linear). Neither family forces more than a handful of contractions
across its entire run. Reaching anywhere near the cubic bound needs a single search to trigger many nested
contractions back to back — a real but more deliberately adversarial shape than either of these, and not one
this page measured.
Time: O(V³) — at most V augmentations total (each one
raises the matching size by exactly one, and the matching size can never exceed V/2), each
driven by one findPath call that does a BFS over O(V + E) edges, where up to
O(V) separate contraction events can fire, each costing O(V) to recompute
lca and rebase every vertex in the newly-folded blossom. O(V) augmentations times
O(V) contractions times O(V) work per contraction gives the standard
O(V³) bound — see Pitfalls above for how far short of it two natural graph families actually
land. Space: O(V + E) for the adjacency lists plus the five length-V
bookkeeping arrays (match, p, base, used,
blossom).
This closes the forward reference named on both Bipartite Matching's and Hopcroft-Karp's own Pitfalls sections, and adds a new question to Choosing a Network Flow Algorithm: not "how many pairs in a two-sided problem," but "how many pairs with no sides at all."