General Graph Matching, in Depth

Where general matching shows up

General matching appears whenever things are paired with things of the same kind. Examples include pairing players or reviewers who can each work with certain others, two-person shift assignments, and pairwise kidney exchanges where incompatible donor-patient pairs swap. The weighted version is a subroutine in Christofides' TSP approximation, which pairs up the odd-degree vertices of a spanning tree. It also appears in the Chinese postman problem and in decoding surface-code quantum error correction, where tools such as PyMatching run minimum-weight perfect matching on syndrome graphs. Chemistry uses perfect matchings to find Kekulé structures of molecules.

In each case the conflict graph is not bipartite. A triangle of three people who can all work together is already an odd cycle. Before using the general algorithm, check: if a BFS two-colouring succeeds, the bipartite tools are simpler and faster.

Where general matching shows up

General matching appears whenever things are paired with things of the same kind. Examples include pairing players or reviewers who can each work with certain others, two-person shift assignments, and pairwise kidney exchanges where incompatible donor-patient pairs swap. The weighted version is a subroutine in Christofides' TSP approximation, which pairs up the odd-degree vertices of a spanning tree. It also appears in the Chinese postman problem and in decoding surface-code quantum error correction, where tools such as PyMatching run minimum-weight perfect matching on syndrome graphs. Chemistry uses perfect matchings to find Kekulé structures of molecules.

In each case the conflict graph is not bipartite. A triangle of three people who can all work together is already an odd cycle. Before using the general algorithm, check: if a BFS two-colouring succeeds, the bipartite tools are simpler and faster.

Augmenting paths and Berge's lemma

Fix a matching M. A vertex is free if no edge of M touches it. An alternating path uses edges that are alternately outside and inside M. An augmenting path is an alternating path whose two ends are both free. It has one more non-matching edge than matching edges. Flipping it (taking the symmetric difference with M) therefore gives a matching one larger.

Berge's lemma (1957): M is maximum if and only if no augmenting path exists. The proof is short. Suppose M' is larger than M. Every vertex has degree at most 2 in the symmetric difference of M and M', so it splits into alternating paths and even cycles. M' has more edges overall, so at least one component holds more M' edges than M edges, and that component is an augmenting path for M.

So every maximum-matching algorithm has the same outer loop: find an augmenting path, flip it, repeat. There are at most V/2 augmentations. All the difficulty is in finding a path when one exists.

Why odd cycles break the bipartite search

The bipartite search grows an alternating tree from a free root. The root is outer (even distance). Its neighbours are inner (odd). The partner of each inner vertex is outer again, and the search continues only from outer vertices. In a bipartite graph each vertex has a fixed parity, so this labelling is consistent.

Now take the graph in the diagram: a five-cycle a-b-c-d-e-a with matching {b-c, d-e}, plus a pendant vertex f joined to b. Vertices a and f are free. Search from a. Then b and e are inner, and their partners c and d are outer. The edge c-d joins two outer vertices. In a bipartite graph that cannot happen. Here it shows an odd cycle. The plain search labelled b as inner, so it never explores the non-matching edge b-f. It reports no augmenting path and stops at a matching of size 2.

Yet the path f-b-c-d-e-a exists: f-b unmatched, b-c matched, c-d unmatched, d-e matched, e-a unmatched. Walk the cycle the other way and b is reached at even distance, so it is really outer. In an odd cycle, every vertex can be reached at both parities. That is the problem the blossom algorithm solves.

Blossoms: shrink, search, lift

A blossom is an odd cycle of length 2k+1 with k matching edges, reached from the root by an even alternating stem. The one cycle vertex not matched inside the cycle is the base. Edmonds' insight was to contract the blossom into a single vertex and continue the search in the smaller graph.

Contraction lemma: if B is a blossom for M, then G has an augmenting path for M exactly when G/B has an augmenting path for M/B. The useful direction is lifting. Suppose the contracted path enters the blossom vertex. Inside the odd cycle, one of the two routes from the entry vertex to the base has even length and alternates correctly. Splice that route in and you have a real augmenting path in G.

Blossoms nest, because a contracted vertex can itself lie on a later odd cycle. Implementations therefore avoid physical contraction. They keep a base[v] array giving the base of the outermost blossom that contains v, and they record enough parent pointers to reconstruct paths. When an outer-outer edge (v, w) appears, the base of the new blossom is the lowest common ancestor of v and w in the alternating tree. This is the same idea as in LCA on trees, found here by walking up both branches. Every vertex in the cycle becomes outer, which is what lets b explore b-f in the example.

A tested implementation

This is the classic BFS formulation of Edmonds' algorithm, O(V³): up to V searches of O(V²) each with an adjacency list. Vertices are 0..n-1. match[v] is v's partner or -1.

from collections import deque

def max_matching(n, adj):
    match = [-1] * n

    def find_augmenting_path(root):
        used = [False] * n      # vertex is outer (even) in the tree
        parent = [-1] * n       # inner vertex -> outer vertex that reached it
        base = list(range(n))   # base of the blossom containing each vertex
        used[root] = True
        q = deque([root])

        def lca(a, b):
            seen = [False] * n
            while True:
                a = base[a]
                seen[a] = True
                if match[a] == -1:
                    break
                a = parent[match[a]]
            while True:
                b = base[b]
                if seen[b]:
                    return b
                b = parent[match[b]]

        def mark_path(v, b, child, in_blossom):
            while base[v] != b:
                in_blossom[base[v]] = in_blossom[base[match[v]]] = True
                parent[v] = child
                child = match[v]
                v = parent[match[v]]

        while q:
            v = q.popleft()
            for to in adj[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if to == root or (match[to] != -1 and parent[match[to]] != -1):
                    cur = lca(v, to)                  # odd cycle: contract it
                    in_blossom = [False] * n
                    mark_path(v, cur, to, in_blossom)
                    mark_path(to, cur, v, in_blossom)
                    for i in range(n):
                        if in_blossom[base[i]]:
                            base[i] = cur
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif parent[to] == -1:
                    parent[to] = v
                    if match[to] == -1:
                        return to, parent             # free vertex: path found
                    used[match[to]] = True
                    q.append(match[to])
        return -1, parent

    for root in range(n):
        if match[root] != -1:
            continue
        v, parent = find_augmenting_path(root)
        while v != -1:                                # flip the path
            pv = parent[v]
            nxt = match[pv]
            match[v], match[pv] = pv, v
            v = nxt
    return match

Two details carry the correctness. The test to == root or parent[match[to]] != -1 asks whether to is already outer, which means an odd cycle has closed. mark_path sets parent pointers in the reverse direction around the cycle, so later path reconstruction can leave the blossom along its even side. That is lifting done lazily, without building the contracted graph. We tested this code against an exhaustive bitmask search on 3,000 random graphs with up to 11 vertices. Do the same with yours:

def brute(n, edges):              # exponential, for testing only
    from functools import lru_cache
    nb = [0] * n
    for u, v in edges:
        nb[u] |= 1 << v; nb[v] |= 1 << u
    @lru_cache(None)
    def f(mask):
        if not mask: return 0
        i = (mask & -mask).bit_length() - 1
        rest = mask & ~(1 << i)
        best, m = f(rest), nb[i] & rest
        while m:
            j = (m & -m).bit_length() - 1
            best = max(best, 1 + f(rest & ~(1 << j)))
            m &= m - 1
        return best
    return f((1 << n) - 1)

Tracing the worked example

Number a..f as 0..5. The outer loop starts at a, which is free. The edges are a-b, b-c, c-d, d-e, e-a and b-f. To match the diagram, suppose M already holds {b-c, d-e}.

1. Pop a. Neighbour b is matched and unvisited, so parent[b] = a and its partner c becomes outer. Neighbour e is handled the same way: parent[e] = a, and d becomes outer.
2. Pop c. Its neighbour d is matched and parent[match[d]] = parent[e] is set, so d is outer and an odd cycle has closed. lca(c, d) walks c, a, then d, e, a and returns base a.
3. The two mark_path calls set parent[c] = d and parent[d] = c. All five cycle vertices get base a, and b and e, previously inner, become outer and are queued.
4. Pop d, which finds nothing new. Pop b: neighbour f has no parent and is free, so parent[f] = b and the search returns f.
5. Flip: f takes b, b's old partner c takes parent[c] = d, d's old partner e takes parent[e] = a. Result: {a-e, b-f, c-d}, a perfect matching.

Starting from an empty matching, the code reaches a perfect matching on this graph by a different route. Augmentation order changes which maximum matching you get, not its size.

Proving optimality: Tutte-Berge

Bipartite matching has König's theorem as its certificate: a vertex cover of the same size. General graphs need a different witness. The Tutte-Berge formula states that the maximum matching size equals the minimum over vertex subsets U of (|V| + |U| - odd(G - U)) / 2, where odd(G - U) counts the components of odd size left after deleting U. The easy direction is intuitive. Each odd component has at least one vertex that must be matched into U or left free, and U can absorb at most |U| of them.

Tutte's theorem is the special case for perfect matchings: one exists exactly when no U leaves more than |U| odd components. Edmonds' algorithm produces the witness for free. When the final search from every free vertex fails, the Gallai-Edmonds decomposition (vertices reachable as even, as odd, or not at all) gives a U that attains the bound. In production, at least assert that the result is a valid matching and that a second search finds no augmenting path. NetworkX provides is_matching, is_maximal_matching and is_perfect_matching for cheap structural checks. Maximal (no edge can be added) is much weaker than maximum.

Choosing an algorithm or library

In Python, networkx.max_weight_matching(G, maxcardinality=True) implements the weighted blossom algorithm. With unit weights it returns a maximum-cardinality matching, as a set of edge pairs. For minimum-weight matchings NetworkX also has min_weight_matching; read its docstring for how it treats graphs with no perfect matching, and use a dedicated solver such as Blossom V for large graphs. For weighted bipartite cases, assignment solvers and flow-based methods stay the better tools.

Failure modes

• Using bipartite code on a non-bipartite graph. Kuhn or Hopcroft-Karp on a graph with odd cycles returns a wrong answer with no error: often a smaller matching, and with some implementations not even a valid one. Test bipartiteness first.
• Forgetting to reset per-search state. base, parent and used must be fresh for every root. Stale bases from an earlier search contract cycles that no longer exist.
• Self-loops and duplicate edges. A self-loop makes a vertex its own neighbour and can corrupt the parity logic. Strip self-loops and deduplicate edges before running.
• Recursion limits. Recursive DFS variants hit Python's default recursion limit on long paths. The BFS version above is iterative.
• Confusing maximal with maximum. Greedy output looks plausible in tests on small graphs and can be half the optimum on adversarial ones.
• Weights by hand. Turning a weighted problem into repeated cardinality runs (thresholding) is usually wrong. Use the weighted algorithm.

What to do next

1. Implement the BFS blossom algorithm above and run it against the brute-force checker on thousands of random graphs before trusting it.
2. Hand-trace the a-f example, then build a nested-blossom case (an odd cycle through a contracted vertex) and trace that too.
3. Add a bipartite check in front, and route bipartite inputs to Hopcroft-Karp.
4. Compare your output sizes with networkx.max_weight_matching(G, maxcardinality=True) on graphs with unit weights.
5. Work through the Tutte-Berge formula on a small graph with no perfect matching, and find the set U that proves it.
6. For a real weighted problem (pairing with costs), model it, solve it with the weighted blossom, and confirm the result beats greedy.