What Is a Perfect Matching Algorithm? Every Vertex Paired, None Left Out

Imagine assigning five interns to five projects. Each intern has skills for a specific subset of projects. You want every intern placed and every project covered. HR is breathing down your neck. Can it be done?

That's a perfect matching problem. And the answer might be no.

Perfect matching sounds narrow until you start seeing it everywhere: resource allocation, DNA sequencing, job scheduling, network routing. Whenever a problem asks whether every item in a group can be paired one-to-one with something else, you're asking whether a perfect matching exists. Knowing when one exists, and which perfect matching algorithm to reach for, is what separates the candidate who spots the pattern from the one who reinvents augmenting paths from scratch at 10 AM in a Google interview.

Matching vs Perfect Matching: The Distinction That Matters

A matching in a graph is a set of edges where no two edges share a vertex. Each edge "consumes" both endpoints.

A maximum matching finds the largest such set. It pairs as many vertices as possible, but some might go unmatched. That's fine. Maximum matching is the participation-trophy version.

A perfect matching is stricter: every single vertex must be covered by exactly one matching edge. Not most vertices. Not "we got pretty close." All of them.

One immediate consequence: a perfect matching can only exist in a graph with an even number of vertices. An odd-vertex graph is missing one potential partner by definition. You can always find a maximum matching; you might never find a perfect one. Life is unfair and so is graph theory.

This distinction matters in interviews. "Does a perfect matching exist?" is a harder question than "find a maximum matching." The answer can be no, and proving it requires understanding the structure of the graph.

See It Work, Then Watch It Break

Take a bipartite graph with workers on the left and jobs on the right:

W1 -- J1, J2
W2 -- J2, J3
W3 -- J1, J4
W4 -- J3, J4

Try one assignment:

• W1 to J1
• W2 to J3
• W3 to J4
• W4 to J3? Already taken.

Back up. Try again:

• W1 to J2
• W2 to J3
• W3 to J1
• W4 to J4

Every worker placed, every job filled. Perfect matching found. Everyone gets pizza.

Now isolate W4 by removing its edges. W4 has no available job, and no reassignment of W1, W2, W3 can fix that. The perfect matching is impossible. W4 goes home. This is why we have exit interviews.

The key insight: one isolated vertex dooms the entire matching. Perfect matching is all-or-nothing. One sad vertex and the whole thing falls apart.

When Does a Perfect Matching Exist?

For bipartite graphs, Philip Hall answered this exactly in 1935 with something called Hall's Marriage Theorem. The name is either charming or concerning depending on your read of 1930s academia, but the math holds up.

Hall's theorem says: a bipartite graph G = (X ∪ Y, E) with |X| = |Y| has a perfect matching if and only if every subset S of X has at least |S| neighbors in Y.

Intuitively, you cannot have a bottleneck where more vertices on one side compete for fewer vertices on the other. If three workers collectively only know two jobs, someone is guaranteed to go unmatched. Hall's condition checks every such subset. You're essentially asking: for every clique of workers, do they collectively know enough jobs?

Here's how the condition fails. Suppose X = {A, B, C} and Y = {1, 2, 3}, with these edges:

A -- 1
B -- 1
C -- 1, 2, 3

The subset {A, B} has only one neighbor (vertex 1). Hall's condition requires at least two neighbors for a two-vertex subset, but you've got one. No perfect matching exists. A and B are both competing for the same one job because they've only bothered to learn one skill. Relatable, honestly.

Hall's theorem is primarily an existence proof, not an algorithm. It tells you whether to bother looking, and it gives you a compact witness for impossibility (the violating subset). Building the matching itself still requires an algorithm.

For general (non-bipartite) graphs, the analogous result is Tutte's theorem: a graph G has a perfect matching if and only if for every subset U of vertices, the number of odd-sized connected components of G minus U is at most |U|. Tutte's condition handles the odd-cycle structure that makes general graphs harder, but it's rarely something you check by hand.

Odd Cycles: Why Bipartite Is the Easy Case

Bipartite graphs have no odd cycles. Every cycle has even length. This makes augmenting path algorithms clean: an alternating path (alternating matched and unmatched edges) that starts and ends at unmatched vertices is guaranteed not to revisit vertices.

General graphs break this. An odd cycle creates a situation where an alternating path can wrap around the cycle and revisit a vertex, making a valid augmenting path look invalid under the simple algorithm.

Edmonds' blossom algorithm (1965) handles this by detecting odd cycles and "contracting" them into single nodes called blossoms, then running augmenting paths on the contracted graph. After augmenting, it expands the blossom back. The algorithm runs in O(V³) time. It is correct for all graphs. It is also notoriously hard to implement, and if you claim otherwise in an interview, you are either lying or you are Jack Edmonds. In standard coding interviews, you will almost never need it.

Perfect Matching Algorithms

For bipartite perfect matching, three approaches dominate:

Algorithm	Time	Best for
Augmenting path DFS	O(VE)	Simple implementation, sparse graphs
Hopcroft-Karp	O(E√V)	Denser graphs, larger V
Reduce to max flow	O(VE) or better	Reusing existing flow code

The augmenting path DFS is the easiest to write from scratch. The idea: try to match each left vertex, and if its preferred right vertex is already taken, recursively try to reroute the existing match elsewhere.

from collections import defaultdict

def has_perfect_matching(num_left: int, edges: list[tuple[int, int]]) -> bool:
    graph: defaultdict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    match_right: dict[int, int] = {}  # right vertex -> matched left vertex

    def try_augment(left: int, visited: set[int]) -> bool:
        for right in graph[left]:
            if right not in visited:
                visited.add(right)
                if right not in match_right or try_augment(match_right[right], visited):
                    match_right[right] = left
                    return True
        return False

    matched_count = 0
    for left in range(num_left):
        if try_augment(left, set()):
            matched_count += 1

    return matched_count == num_left

The same logic in TypeScript:

function hasPerfectMatching(numLeft: number, edges: [number, number][]): boolean {
    const graph = new Map<number, number[]>();
    for (const [u, v] of edges) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u)!.push(v);
    }

    const matchRight = new Map<number, number>();

    function tryAugment(left: number, visited: Set<number>): boolean {
        for (const right of graph.get(left) ?? []) {
            if (!visited.has(right)) {
                visited.add(right);
                if (!matchRight.has(right) || tryAugment(matchRight.get(right)!, visited)) {
                    matchRight.set(right, left);
                    return true;
                }
            }
        }
        return false;
    }

    let matched = 0;
    for (let left = 0; left < numLeft; left++) {
        if (tryAugment(left, new Set())) matched++;
    }
    return matched === numLeft;
}

Hopcroft-Karp speeds this up by using BFS to find all shortest augmenting paths simultaneously, then augmenting all of them in one DFS pass. The number of BFS phases is O(√V), each phase takes O(E), giving O(E√V) total. For LeetCode-style inputs you often do not need this, but knowing it exists matters when you're analyzing complexity and want to look like someone who reads papers.

Memory Is O(V + E)

Any matching algorithm needs adjacency lists at O(V + E), O(V) to record the pairing, and O(V) for the visited set per augmentation.

Total space is O(V + E), dominated by storing the graph. Nothing exotic here.

The Max Flow Connection

Bipartite perfect matching has a textbook reduction to max flow. Add a source with capacity-1 edges to every left vertex, and a sink with capacity-1 edges from every right vertex. Set every original edge to capacity 1. A max flow equal to |X| is exactly a perfect matching.

This means any max flow implementation works for matching. It also makes it easy to enumerate all edges that participate in some perfect matching, which is useful when the problem asks for multiple valid assignments. For the full algorithm behind max flow, see Maximum Flow and Minimum Cut.

Recognizing Matching Problems in Interviews

Most interview matching problems do not announce themselves with "this is a matching problem." They show up as:

• "Can we schedule every task to a unique machine given capacity constraints?"
• "Is there a way to pair all n elements such that each pair satisfies a property?"
• "Given students and dorm rooms, can we place everyone with no conflicts?"

If the problem asks you to pair every item in a group without reuse, against a constraint on which pairs are valid, you're looking at a matching problem.

The recognition path:

1. Model it as a graph. Vertices are the things being paired; edges are valid pairings.
2. If the graph is bipartite (two groups, edges only between groups), you're in the easy case.
3. Check that both sides have equal size. If not, a perfect matching is immediately impossible.
4. Apply augmenting path DFS or Hopcroft-Karp.
5. Return whether the matching size equals the group size.

See Bipartite Matching: The Assignment Problem for the full algorithm walkthrough, and What Is a Bipartite Graph? for the graph structure behind it. For the O(E√V) algorithm, see Hopcroft-Karp.

If you want to practice explaining this reasoning out loud under real interview pressure, SpaceComplexity runs voice-based mock interviews on graph problems, including matching, flow, and the edge cases that trip candidates up.

Common Mistakes (Or: A Complete Taxonomy of How to Lose a Matching Interview)

Confusing maximum matching with perfect matching. A maximum matching always exists. A perfect matching might not. Check |X| = |Y| first, then verify the matching size actually equals |X|. These are different questions and the interviewers know the difference.

Missing the bipartite structure. Assignment problems are bipartite in disguise more often than not. Draw the problem as two groups before reaching for anything general. Bipartite algorithms are O(E√V). General graph algorithms are O(V³). That gap matters.

Reaching for Edmonds' blossom when it's not needed. If you can confirm the graph is bipartite, the simple DFS approach works. Blossom handles general graphs but is notoriously difficult to implement correctly. Don't bring it up in an interview unless you can actually code it. "I'd use the blossom algorithm" and then silence is worse than saying nothing.

Treating Hall's condition as an algorithm. Hall's theorem tells you whether a perfect matching exists, not how to find it. You still need an augmenting path algorithm to build the actual matching. The theorem is a proof tool, not a solution.

Further Reading

• Perfect Matching (Wikipedia)
• Hall's Marriage Theorem (Wikipedia)
• Tutte's Theorem (Wikipedia)
• Blossom Algorithm (Wikipedia)
• Maximum Bipartite Matching (GeeksforGeeks)