x. General Matching

Maximum matching in a non-bipartite graph. Berge’s theorem still holds (Bipartite Matching), but an odd cycle lets the alternating search reach a vertex with both parities, so the plain DFS is wrong. Edmonds: contract such odd cycles (blossoms) and keep searching. First check whether the graph is secretly bipartite; if only the size is needed, the Tutte matrix rank is 15 lines.

Method	Time	Gives
Edmonds’ blossom (BFS + contraction)	$O(V^3)$	the matching, $V\le 1000$ comfortably
Tutte matrix rank (random)	$O(V^3)$	size; with Mucha–Sankowski elimination also the matching
Micali–Vazirani	$O(E\sqrt{V})$	theory — notoriously hard to implement correctly
greedy on trees / forests	$O(V)$	match a leaf to its parent
Gabow scaling (weighted)	$O(V^{3/4}E\log C)$	theoretical
Blossom V (Kolmogorov)	$O(V^3)$	the standard weighted implementation used in practice — see Weighted General Matching

Checklist before reaching for any of this: (1) is the graph secretly bipartite — run a 2-colouring first, many “general” graphs in problems are bipartite by construction; (2) only existence or the size needed — Tutte matrix; (3) the actual matching, unweighted — blossom; (4) weighted — Blossom V, or model it as min-cost flow if step 1 found it’s actually bipartite.

Edmonds’ blossom algorithm

struct Blossom {
    int n; vector<vector<int>> g; vector<int> mt, p, base, q; vector<char> used, bl;
    Blossom(int n) : n(n), g(n), mt(n, -1), p(n), base(n), q(n), used(n), bl(n) {}
    void addEdge(int u, int v) { if (u != v) g[u].push_back(v), g[v].push_back(u); }
    int lca(int a, int b) {
        vector<char> seen(n);
        for (;;) { a = base[a]; seen[a] = 1; if (mt[a] < 0) break; a = p[mt[a]]; }
        for (;;) { b = base[b]; if (seen[b]) return b; b = p[mt[b]]; }
    }
    void markPath(int v, int b, int ch) {
        while (base[v] != b) { bl[base[v]] = bl[base[mt[v]]] = 1; p[v] = ch; ch = mt[v]; v = p[mt[v]]; }
    }
    int findPath(int root) {                                   // free vertex at the end of an augmenting path, or -1
        fill(all(used), 0); fill(all(p), -1); iota(all(base), 0);
        int qh = 0, qt = 0; used[root] = 1; q[qt++] = root;
        while (qh < qt) {
            int v = q[qh++];
            for (int to : g[v]) {
                if (base[v] == base[to] || mt[v] == to) continue;
                if (to == root || (mt[to] >= 0 && p[mt[to]] >= 0)) {      // even-even edge: a blossom
                    int cb = lca(v, to); fill(all(bl), 0);
                    markPath(v, cb, to); markPath(to, cb, v);
                    for (int i = 0; i < n; i++) if (bl[base[i]]) { base[i] = cb; if (!used[i]) used[i] = 1, q[qt++] = i; }
                } else if (p[to] < 0) {                                    // grow the tree
                    p[to] = v;
                    if (mt[to] < 0) return to;
                    used[mt[to]] = 1; q[qt++] = mt[to];
                }
            }
        }
        return -1;
    }
    int run() {
        int res = 0;
        for (int v = 0; v < n; v++) if (mt[v] < 0) for (int to : g[v]) if (mt[to] < 0) { mt[v] = to, mt[to] = v, res++; break; }
        for (int v = 0; v < n; v++) if (mt[v] < 0) {
            int u = findPath(v); if (u < 0) continue;
            res++;
            while (u >= 0) { int pv = p[u], ppv = mt[pv]; mt[u] = pv, mt[pv] = u, u = ppv; }
        }
        return res;
    }
};

used marks the even (outer) vertices of the search tree, including every vertex absorbed into a blossom; base maps each vertex to its current blossom base; p stores the tree edge into each odd vertex (rewired inside blossoms so that the path can be lifted).

Proof: why contraction is safe, and why one pass over roots suffices

Lifting. A blossom is an odd cycle $b=c_0,c_1,\dots ,c_{2k}$ with matching edges $c_1{c}_2,c_3{c}_4,\dots ,c_{2k-1}{c}_{2k}$; its base $b$ is the only vertex not matched inside it and is reached from the root by an even alternating path (the stem). From $c_i$ with $i$ even, walking $c_i,c_{i-1},\dots ,c_0$ starts with the matched edge $c_{i-1}{c}_i$ and has even length $i$; with $i$ odd, walking $c_i,c_{i+1},\dots ,c_{2k},c_0$ starts with the matched edge $c_i{c}_{i+1}$ and has even length $2k+1-i$. So every blossom vertex has an even alternating path to $b$, an augmenting path of $G/B$ through the contracted vertex lifts to one of $G$ by inserting that detour, and markPath stores these detours in p.

No path is lost. Suppose $G$ has an augmenting path. Flip the stem: the matching keeps its size, $b$ becomes free and $B$ is still an odd cycle whose only vertex not matched inside is $b$. Take an augmenting path $P$ for this matching. If $P$ avoids $B$, it is augmenting in $G/B$. Otherwise, since $b$ is the only free vertex of $B$, some endpoint $f$ of $P$ lies outside $B$; follow $P$ from $f$ to its first vertex in $B$. The edge entering $B$ is unmatched (the matched edges of $B$‘s vertices other than $b$ stay inside $B$, and $b$ is free), so this prefix is an augmenting path in $G/B$ ending at the free contracted vertex. Thus the flipped matching is not maximum in $G/B$, and neither is the original one (same size), so by Berge $G/B$ has an augmenting path for it. Hence the search on the contracted graph finds an augmenting path from the root iff one exists in $G$ from the root’s tree.

One pass. Claim: if no augmenting path starts at $u$ for $M$, none starts at $u$ for $M^{\prime }=M△P$ ($P$ augmenting between $x$ and $y$). Let $Q$ be $M^{\prime }$-augmenting from $u$; if $Q$ misses $P$, it is $M$-augmenting. Else let $t$ be the first vertex of $Q$ on $P$. The $Q$-edge entering $t$ is not on $P$ (its other end is not on $P$), and $t$‘s $M^{\prime }$-edge is on $P$, so the entering edge is unmatched in $M^{\prime }$ and in $M$. If $t\in \{x,y\}$, $Q[u..t]$ is already $M$-augmenting. Otherwise continue from $t$ along $P$ through $t$‘s $M$-matched edge to the end of $P$; the result alternates, ends at an $M$-free endpoint and is simple. Contradiction. So each vertex needs to be tried as a root once, and after the loop no free vertex starts an augmenting path: the matching is maximum by Berge.

Time. One search contracts at most $n/2$ blossoms at $O(n)$ each and scans each edge $O(1)$ times per endpoint: $O(n^2+m)$; $n$ roots give $O(n^3)$.

Theory

• Tutte–Berge formula: $\nu (G)=\frac{1}{2}{\min }_{U\subseteq V}(|V|+|U|-\text{odd}(G-U))$, where odd counts odd components. Tutte’s theorem: a perfect matching exists iff $\text{odd}(G-U)\le |U|$ for all $U$.
• Gallai–Edmonds decomposition: $D$ = vertices missed by some maximum matching, $A$ = neighbours of $D$ outside $D$, $C$ = the rest. Every maximum matching matches $A$ into distinct components of $G[D]$, each component of $G[D]$ is factor-critical (deleting any vertex leaves a perfect matching), and $G[C]$ has a perfect matching. $U=A$ attains Tutte–Berge.
• Petersen: every bridgeless cubic graph has a perfect matching. Factor-critical graphs are exactly those with an odd ear decomposition.
• Gallai’s ${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)=n$ (max matching + min edge cover) holds in all graphs; vertex cover and independent set are NP-hard outside bipartite graphs.

vector<int> gallaiEdmonds(Blossom& B) {                 // after B.run(): 0 = D, 1 = A, 2 = C
    int n = B.n; vector<int> type(n, 2);
    for (int r = 0; r < n; r++) if (B.mt[r] < 0) { B.findPath(r); for (int v = 0; v < n; v++) if (B.used[v]) type[v] = 0; }
    for (int v = 0; v < n; v++) if (type[v] == 0) for (int u : B.g[v]) if (type[u] == 2) type[u] = 1;
    return type;
}

Proof: Tutte–Berge and the decomposition

Upper bound: for any $U$, every odd component of $G-U$ either has an unmatched vertex or sends a matching edge to $U$; at most $|U|$ can do the latter, so at least $\text{odd}(G-U)-|U|$ vertices are unmatched and $2\nu \le |V|-\text{odd}(G-U)+|U|$.

Even vertices = $D$: for a maximum matching $M$, $v$ is missed by some maximum matching iff $v$ is reachable from a free vertex by an even alternating path (flip it; conversely $M△M^{\prime }$ gives such a path, as in the bipartite case). After the last search from a free root fails, used marks exactly the vertices with an even alternating path from that root (blossom vertices have one by the lifting argument), so the union over free roots is $D$.

Equality (Gallai–Edmonds): take the final search forest from all free roots. Odd (inner) vertices are matched to even ones, and there is no even–even edge between different trees or blossoms (it would give an augmenting path) and no edge from $D$ to $C$ (it would make the $C$ vertex odd, i.e. in $A$). So the components of $G[D]$ are the contracted blossoms and single even vertices, each odd and factor-critical (a blossom minus any vertex has a perfect matching by rotating around the cycle), the $A$ vertices are the odd tree vertices each matched into a different $D$ component, and $C$ is perfectly matched within itself. Counting with $U=A$: the unmatched vertices are exactly one per $D$ component not matched to $A$, i.e. $\text{odd}(G-A)-|A|$, which meets the upper bound.

Tutte matrix (randomised)

Put a random $x_{uv}$ at $(u,v)$ and $-x_{uv}$ at $(v,u)$ for each edge, modulo a large prime. Then $\text{rank}=2\nu$ with probability $\ge 1-n/p$. To extract a matching, pad with extra vertices joined to everything until the matrix is invertible, invert it, and repeatedly pick an edge $(i,j)$ with $A_{ij}^{-1}\ne 0$, eliminating rows and columns $i,j$ (Rabin–Vazirani / Mucha–Sankowski elimination).

namespace tutte {
const ll MOD = 1'000'000'007; mt19937_64 rng(98765);
ll pw(ll a, ll e) { ll r = 1; for (a %= MOD; e; e >>= 1, a = a * a % MOD) if (e & 1) r = r * a % MOD; return r; }
int gauss(vector<vector<ll>>& m) {                           // reduced row echelon form, returns the rank
    int R = sz(m), C = R ? sz(m[0]) : 0, rk = 0;
    for (int c = 0; c < C && rk < R; c++) {
        int row = -1; for (int j = rk; j < R; j++) if (m[j][c]) { row = j; break; }
        if (row < 0) continue;
        swap(m[row], m[rk]); ll inv = pw(m[rk][c], MOD - 2);
        for (int k = c; k < C; k++) m[rk][k] = m[rk][k] * inv % MOD;
        for (int j = 0; j < R; j++) if (j != rk && m[j][c]) { ll v = m[j][c]; for (int k = c; k < C; k++) m[j][k] = (m[j][k] + MOD - v * m[rk][k] % MOD) % MOD; }
        rk++;
    }
    return rk;
}
vector<vector<ll>> build(int n, const vector<pair<int, int>>& E) {
    vector<vector<ll>> m(n, vector<ll>(n));
    for (auto [a, b] : E) if (a != b) { ll r = rng() % (MOD - 1) + 1; m[a][b] = r, m[b][a] = MOD - r; }
    return m;
}
int matchingSize(int n, const vector<pair<int, int>>& E) { auto m = build(n, E); return gauss(m) / 2; }
vector<pair<int, int>> matching(int n, const vector<pair<int, int>>& E) {
    auto mat = build(n, E), tmp = mat; int r = gauss(tmp), M = 2 * n - r;
    for (auto& row : mat) row.resize(M);
    mat.resize(M, vector<ll>(M));
    vector<vector<ll>> A;
    while (A.empty()) {                                      // join M - n new vertices to all old ones
        for (int i = 0; i < n; i++) for (int j = n; j < M; j++) { ll x = rng() % (MOD - 1) + 1; mat[i][j] = x, mat[j][i] = MOD - x; }
        vector<vector<ll>> x(M, vector<ll>(2 * M));
        for (int i = 0; i < M; i++) { x[i][i + M] = 1; for (int j = 0; j < M; j++) x[i][j] = mat[i][j]; }
        if (gauss(x) == M) { A.assign(M, vector<ll>(M)); for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) A[i][j] = x[i][j + M]; }
    }
    vector<char> has(M, 1); vector<pair<int, int>> ret;
    for (int it = 0; it < M / 2; it++) {
        int fi = -1, fj = -1;
        for (int i = 0; i < M && fi < 0; i++) if (has[i]) for (int j = i + 1; j < M; j++) if (has[j] && A[i][j] && mat[i][j]) { fi = i, fj = j; break; }
        if (fi < 0) break;                                   // probability about n / MOD
        has[fi] = has[fj] = 0;
        if (fj < n) ret.push_back({fi, fj});
        for (int sw = 0; sw < 2; sw++) {
            ll a = pw(A[fi][fj], MOD - 2);
            for (int i = 0; i < M; i++) if (has[i] && A[i][fj]) { ll b = A[i][fj] * a % MOD; for (int j = 0; j < M; j++) A[i][j] = (A[i][j] + MOD - A[fi][j] * b % MOD) % MOD; }
            swap(fi, fj);
        }
    }
    return ret;
}
}

Proof: rank of the Tutte matrix

Perfect matchings. If $G$ has a perfect matching $M$, substituting $x_e=1$ on $M$ and $0$ elsewhere makes $T$ block-diagonal with blocks \begin{psmallmatrix}0&1\\-1&0\end{psmallmatrix}, determinant $1$, so $\det T\not\equiv 0$. Conversely expand $\det T={\sum }_{\sigma }\text{sgn}(\sigma ){\prod }_i{T}_{i\sigma (i)}$. Terms of permutations with an odd cycle cancel: reversing the odd cycle containing the smallest such vertex keeps the cycle type (so the sign) and flips an odd number of entries $T_{ij}\to T_{ji}=-T_{ij}$ (fixed points have $T_{ii}=0$ anyway). So if $\det T\not\equiv 0$ some permutation with only even cycles uses edges of $G$ everywhere, and alternate edges of each cycle form a perfect matching.

Rank $=2\nu$. For a skew-symmetric $A$, if the rows $I$ are a basis of the row space then the principal submatrix $A_{II}$ is nonsingular: write the other rows as $A_{J\ast }=X{A}_{I\ast }$; skew-symmetry gives $A_{IJ}=-A_{JI}^{\mathsf{T}}=-(X{A}_{II}{)}^{\mathsf{T}}=A_{II}{X}^{\mathsf{T}}$, so a vector $y\ne 0$ with $y^{\mathsf{T}}{A}_{II}=0$ would give $y^{\mathsf{T}}{A}_{I\ast }=0$, contradicting independence. Hence the rank is the largest nonsingular principal submatrix; a principal submatrix on $S$ is the Tutte matrix of $G[S]$, nonsingular iff $G[S]$ has a perfect matching, and the largest such $S$ has $2\nu$ vertices. Random values: the relevant minor is a nonzero polynomial of degree $\le n$, so by Schwartz–Zippel it vanishes at a random point mod $p$ with probability $\le n/p$.

Extraction. After padding, a perfect matching exists (new vertices are joined to everything) and $T$ is invertible w.h.p. Jacobi’s complementary-minor identity gives $\det ((T^{-1}{)}_{\{i,j\},\{i,j\}})=\det T_{V\setminus \{i,j\}}/\det T$, and the left side is $((T^{-1}{)}_{ij}{)}^2$ since $T^{-1}$ is skew-symmetric. So $(T^{-1}{)}_{ij}\ne 0$ iff the Tutte matrix of $G-i-j$ is nonsingular, i.e. (w.h.p.) iff $G-i-j$ has a perfect matching; an edge $(i,j)$ with this property can be taken. The inverse of the remaining matrix is the Schur complement of the $\{i,j\}$ block in $T^{-1}$, which the two pivot steps compute in $O(n^2)$; $n/2$ rounds give $O(n^3)$.

Patterns

• Pair up items with compatibility on a general graph: blossom; “maximum number of disjoint pairs” questions.
• Trees and forests: greedily match a deepest leaf with its parent ($O(n)$, optimal by an exchange argument; the same works for maximum matching on cacti with a DP).
• Edge cover / independent pairs: $\rho =n-\nu$ when there are no isolated vertices.
• Weighted: Weighted General Matching; with few vertices ($\le 20$) a bitmask DP (pair the lowest unpaired vertex).
• Graph games: in the undirected vertex geography game (players alternately extend a path from a token), the first player wins iff the start vertex is in every maximum matching, i.e. $v\notin D$ (Gallai–Edmonds).