General Matching

Maximum matching in a non-bipartite graph. The augmenting-path idea from bipartite matching still applies (Berge’s theorem holds for all graphs), but odd cycles break the naive search.

Why odd cycles break things

In a bipartite graph, an alternating path’s parity at each vertex is determined by which side it is on. In a general graph, an odd cycle can be entered at one vertex and left with either parity — so a vertex may be reachable by both an even-length and an odd-length alternating path, and a plain BFS/DFS misses augmenting paths that require the “wrong” parity.

Blossoms

Edmonds’ insight: an odd cycle reachable by an even-length alternating path is a blossom. Contract it to a single vertex. The key lemma:

The graph has an augmenting path iff the graph with the blossom contracted has one.

So: search, contract blossoms as you find them, augment in the contracted graph, then expand back and lift the augmenting path. This is Edmonds’ Blossom algorithm — the first polynomial algorithm for general matching, and historically the paper where the notion of “polynomial time = efficient” was articulated.

The algorithms

Algorithm	Time	Practicality
Blossom	$O(V^3)$	the one to use — handles $V\le 500$ easily
Micali-Vazirani	$O(E\sqrt{V})$	notoriously hard to implement correctly
Gabow scaling (weighted)	$O(V^{3/4}E\log C)$	theoretical
Blossom V (Kolmogorov)	$O(V^3)$	the standard weighted implementation in practice
Tutte matrix (existence only)	$O(V^{\omega })$ randomized	15 lines — see below

Tutte matrix — the cheap trick

To decide whether a perfect matching exists (without constructing it), build the skew-symmetric Tutte matrix:

$T_{ij}=\{\begin{array}{ll}{x}_{ij}& (i,j)\in E,i<j\\ -x_{ji}& (i,j)\in E,i>j\\ 0& \text{otherwise}\end{array}$

Tutte’s theorem: $G$ has a perfect matching iff $\det T\not\equiv 0$ as a polynomial.

Substitute random values mod a large prime and compute the determinant by Gaussian elimination. By Schwartz-Zippel the failure probability is $O(n/p)$ — negligible. Rank$/2$ even gives the size of the maximum matching.

// existence of a perfect matching, O(n^3), randomized
bool hasPerfectMatching(int n, vector<pair<int,int>>& edges, long long MOD) {
    vector<vector<long long>> T(n, vector<long long>(n, 0));
    for (auto [u, v] : edges) {
        long long r = rng() % MOD;
        T[u][v] = r; T[v][u] = MOD - r;
    }
    return rank(T, MOD) == n;
}

Theory worth knowing

Tutte-Berge formula. The maximum matching size is
$\frac{1}{2}\left(n-{\max }_{U\subseteq V}(\mathrm{odd}(G-U)-|U|)\right)$
where $\mathrm{odd}(\cdot )$ counts components of odd size. It is the general-graph analogue of König’s theorem.

Tutte’s theorem. A perfect matching exists iff $\mathrm{odd}(G-U)\le |U|$ for every $U$.

Petersen’s theorem. Every bridgeless cubic graph has a perfect matching.

Unlike the bipartite case, minimum vertex cover and maximum independent set remain NP-hard on general graphs — König’s equality is exactly what fails.

When you actually need it

General matching appears far less often than bipartite matching, and when it does the graph is usually small. Checklist:

1. Is the graph secretly bipartite? Run a 2-colouring first — many “general” graphs in problems are bipartite by construction.
2. Do you only need existence or the size? Use the Tutte matrix.
3. Do you need the actual matching, unweighted? Blossom.
4. Weighted? Blossom V, or model it as min-cost flow if the graph turns out bipartite.

See also: Blossom Algorithm · Bipartite Matching · Determinant