# Maximum cardinality matching
A **maximum cardinality matching** is a matching of largest possible size in a graph: a set of edges no two of which share an endpoint, chosen so that the number of edges is as large as possible. Such a matching is not always unique, and finding one is a classic problem of combinatorial optimization, solvable in polynomial time in both bipartite and general graphs.[1](https://networkx.org/documentation/networkx-2.6.2/reference/algorithms/generated/networkx.algorithms.bipartite.matching.hopcroft_karp_matching.html)
| Key fact | Detail |
|---|---|
| Definition | A matching is a set of edges that do not share any nodes; a maximum cardinality matching is one with the most edges possible, and it is not always unique[1](https://networkx.org/documentation/networkx-2.6.2/reference/algorithms/generated/networkx.algorithms.bipartite.matching.hopcroft_karp_matching.html) |
| Optimality test | A matching M is maximum-cardinality if and only if there is no augmenting path with respect to M[2](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/bipartite_maximum_matching/augmenting_paths.html) |
| Bipartite case | The Hopcroft–Karp algorithm (1973) finds a maximum matching in a bipartite graph with n vertices and m edges in time proportional to (m + n)√n, in at most 2√n phases[3](https://web.eecs.umich.edu/~pettie/matching/Hopcroft-Karp-bipartite-matching.pdf) • [4](https://www.cs.tau.ac.il/~zwick/grad-algo-13/match.pdf) |
| General graphs | Edmonds' blossom algorithm (described in *Paths, Trees, and Flowers*, 1965) was the first good algorithm for a graph problem outside the "unimodular" mold, with complexity he conservatively pegged at O(n^4)4)[5](https://nvlpubs.nist.gov/nistpubs/sp958-lide/html/140-144.html) • [19](https://nvlpubs.nist.gov/nistpubs/sp958-lide/140-144.pdf) |
| Fastest general algorithm | The Micali–Vazirani algorithm (1980) runs in O(√|V|·|E|) time and remains the most efficient known algorithm for the problem; its first complete correctness proof appeared in 2020[6](https://arxiv.org/abs/2012.03582) • [7](https://www.researchgate.net/publication/221499631_An_Osqrtv_E_Algorithm_for_Finding_Maximum_Matching_in_General_Graphs) |
| Recent bipartite record | Chen et al. (2022) achieved m1+o(1) time for bipartite matching; Chuzhoy and Khanna (2024) gave a purely combinatorial \( \tilde{O}(m^{1/3} n^{5/3}) \) algorithm[8](https://arxiv.org/abs/2312.12584) |
## Matchings and augmenting paths
The central tool of every matching algorithm is the augmenting path. An augmenting path with respect to a matching M is an alternating path, one whose edges alternate between edges in M and edges not in M, whose two endpoints are unmatched by M. Flipping the status of every edge along such a path produces a new matching with exactly one more edge: for an augmenting path P, the symmetric difference \( M' = M \oplus P \) is a matching of cardinality \( |M'| = |M| + 1 \).[2](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/bipartite_maximum_matching/augmenting_paths.html)
This yields a complete characterization of optimality: a matching M is a maximum-cardinality matching if and only if there is no augmenting path in the graph with respect to M. If M is not maximum, taking a larger matching M' and decomposing \( M \oplus M' \) shows that one of its paths must be an augmenting path for M.[2](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/bipartite_maximum_matching/augmenting_paths.html) The resulting generic algorithm starts with the empty matching and repeatedly finds an augmenting path and augments along it, stopping when no such path exists.[4](https://www.cs.tau.ac.il/~zwick/grad-algo-13/match.pdf)
## The bipartite case
In a bipartite graph, whose vertices fall into two sets with every edge joining one vertex from each set, the task becomes a maximum flow problem: computing a best matching amounts to computing a maximum s-t flow in a directed graph whose edges each have capacity one, and applying the basic Ford–Fulkerson method to that network yields an O(mn)-time algorithm.[8](https://arxiv.org/abs/2312.12584)
**Hopcroft–Karp.** In 1973 John E. Hopcroft and [Richard M. Karp](https://www.edgepedia.org/richard-m-karp) showed how to speed up this simple scheme. Instead of finding a single augmenting path at a time, their algorithm uses breadth-first and depth-first search to find a maximal collection of internally disjoint augmenting paths of shortest possible length in each phase, improving the runtime to O(m√n).[8](https://arxiv.org/abs/2312.12584) The analysis shows that the shortest augmenting paths found in successive phases grow strictly longer, so after √n phases the matching is within √n edges of maximum, and a maximum matching is found after at most 2√n phases.[4](https://www.cs.tau.ac.il/~zwick/grad-algo-13/match.pdf)
Bipartite maximum matching is also tied to vertex covers by Kőnig's theorem: in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover, and the alternating forest built by the matching algorithm constructs such a cover in O(m) additional time. For general graphs, by contrast, minimum vertex cover is NP-complete.[4](https://www.cs.tau.ac.il/~zwick/grad-algo-13/match.pdf)
## General graphs and blossoms
In graphs that are not bipartite, the naive strategy of searching for augmenting paths one at a time still works but is slow: finding an augmenting path takes O(nm) time and any matching can be augmented at most n/2 times, giving an O(n2m)-time algorithm.[9](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/general_maximum_cardinality_matching/intro.html)
**The blossom algorithm.** [Jack Edmonds](https://www.edgepedia.org/jack-edmonds) found an efficient algorithm for the maximum matching problem in 1961, during a summer workshop held at the [RAND Corporation](https://www.edgepedia.org/rand-corporation) in [Santa Monica, California](https://www.edgepedia.org/santa-monica-california); he laid it out in his 1965 paper *Paths, Trees, and Flowers*, estimating its complexity conservatively as O(n4). The algorithm runs alternating breadth-first searches from all unmatched vertices; when it encounters a particular type of odd cycle, called a blossom, formed by a path in the alternating forest plus one edge not in the forest, it contracts the blossom to a single vertex and recurses on the smaller graph. An augmenting path in the contracted graph lifts back to one in the original.[5](https://nvlpubs.nist.gov/nistpubs/sp958-lide/html/140-144.html) • [9](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/general_maximum_cardinality_matching/intro.html)
The breakthrough was conceptual as well as computational. All good graph-theoretical algorithms known at the time addressed "unimodular" problems such as shortest path and network flow, which could be formulated as integrality-preserving linear programs; Edmonds' matching algorithm was the first instance of a good algorithm for a problem outside that mold. The paper also contributed a generalization of Kőnig's theorem holding for matchings in all kinds of graphs, not just bipartite ones.[5](https://nvlpubs.nist.gov/nistpubs/sp958-lide/html/140-144.html) In recognition of this work and related contributions, Edmonds received the John von Neumann Theory Prize from INFORMS in 1985.[10](https://www.nist.gov/mathematics-statistics/first-mathematical-theory-efficient-combinatorial-algorithms-jack-edmonds)
**Micali–Vazirani.** Just as bipartite matching was improved from O(nm) to O(m√n), Edmonds' algorithm has been reduced to O(nm) and, by combining its ideas with the phase framework of Hopcroft–Karp, to O(m√n).[9](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/general_maximum_cardinality_matching/intro.html) The Micali–Vazirani algorithm of 1980 achieves O(√|V|·|E|) time by working in phases, each finding a maximal set of disjoint minimum-length augmenting paths, with a special way of handling blossoms that permits an O(|E|) implementation of a phase.[7](https://www.researchgate.net/publication/221499631_An_Osqrtv_E_Algorithm_for_Finding_Maximum_Matching_in_General_Graphs) This bound has stood since 1980, and the algorithm remains the most efficient known for general-graph maximum cardinality matching; its first complete and correct proof of correctness was given by Vijay V. Vazirani in 2020.[6](https://arxiv.org/abs/2012.03582)
## The algorithmic record
The running times form a clear progression. For bipartite graphs, Hopcroft–Karp's O(m√n) stood for decades except on very dense graphs, where fast matrix multiplication gives O(n2.371). In 2013 Madry introduced continuous, interior-point-based techniques achieving much faster runtimes on sparse graphs, a line culminating in the 2022 result of Chen et al. that solves maximum bipartite matching in m1+o(1) time. Chuzhoy and Khanna answered the question of whether continuous techniques are essential by giving a purely combinatorial \( \tilde{O}(m^{1/3} n^{5/3}) \)-time deterministic algorithm, which outperforms Hopcroft–Karp on graphs with \( m = \omega(n^{7/4}) \) and also beats the matrix multiplication approach on dense graphs; a 2024 follow-up gives a randomized n2+o(1)-time combinatorial algorithm.[8](https://arxiv.org/abs/2312.12584) • [11](https://arxiv.org/abs/2405.20861)
Worst-case bounds are not the whole story. An average-case analysis shows that augmenting-path algorithms such as Hopcroft–Karp and Micali–Vazirani, with worst-case running time O(m√n), run in O(m log n) time with high probability on random graphs.[12](https://www.cs.au.dk/~gerth/alcom-ft/TR/ALCOMFT-TR-03-111.html) Phase-based algorithms are also adaptive to structure: they run in linear time on several graph classes and in O(√k·m) time on graphs that are k vertex deletions away from such classes, although the phase framework itself still requires Ω(√n) phases, and hence Ω(√n·m) time, even on paths, cographs, and bipartite chain graphs.[13](https://arxiv.org/abs/1904.11244) Beyond combinatorial methods, a randomized algebraic algorithm published in 1989 works on the Tutte matrix of the graph; it is slower than the best known combinatorial algorithms but conceptually simple and easy to program.[14](https://www.sciencedirect.com/science/article/pii/0196677489900059)
## Applications and computation
Maximum cardinality matching appears wherever pairs must be formed as completely as possible. In kidney exchange programs, an undirected graph of patient-donor pairs is built and the goal is to find a maximum cardinality matching of compatible exchanges.[15](https://www.cse.iitb.ac.in/~swaprava/courses/cs6002/scribed/lec03.pdf) Student-to-project allocation problems likewise build on maximum-cardinality matchings, often with preferences layered on top.[16](https://arxiv.org/abs/1403.0751) In observational statistics, cardinality matching finds the largest possible number of matched pairs of exposed and unexposed individuals with specified baseline characteristics.[17](https://arxiv.org/abs/2201.04276)
General-purpose software exposes the problem directly. NetworkX provides `hopcroft_karp_matching` (also aliased as `maximum_matching`) for bipartite graphs, returning the matching as a dictionary in which unmatched nodes do not appear as keys, and a `max_weight_matching` function whose `maxcardinality` flag computes the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings; its implementation takes O(n3) time.[1](https://networkx.org/documentation/networkx-2.6.2/reference/algorithms/generated/networkx.algorithms.bipartite.matching.hopcroft_karp_matching.html) • [18](https://networkx.org/documentation/stable/_modules/networkx/algorithms/matching.html)
## References
1. [hopcroft_karp_matching, NetworkX 2.6.2 documentation](https://networkx.org/documentation/networkx-2.6.2/reference/algorithms/generated/networkx.algorithms.bipartite.matching.hopcroft_karp_matching.html)
2. [Augmenting Paths, Algorithms II, Dalhousie University](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/bipartite_maximum_matching/augmenting_paths.html)
3. [Hopcroft, J. E. and Karp, R. M. (1973). An n^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal on Computing](https://web.eecs.umich.edu/~pettie/matching/Hopcroft-Karp-bipartite-matching.pdf)
4. [Lecture notes on matching algorithms, U. Zwick, Tel Aviv University](https://www.cs.tau.ac.il/~zwick/grad-algo-13/match.pdf)
5. [Maximum Matching (Blossom) chapter, NIST](https://nvlpubs.nist.gov/nistpubs/sp958-lide/html/140-144.html)
6. [Vazirani, V. V. (2020). A Proof of the MV Matching Algorithm, arXiv](https://arxiv.org/abs/2012.03582)
7. [Micali, S. and Vazirani, V. V. (1980). An O(√|V|·|E|) Algorithm for Finding Maximum Matching in General Graphs, FOCS](https://www.researchgate.net/publication/221499631_An_Osqrtv_E_Algorithm_for_Finding_Maximum_Matching_in_General_Graphs)
8. [Chuzhoy, J. and Khanna, S. (2023). A Faster Combinatorial Algorithm for Maximum Bipartite Matching, arXiv](https://arxiv.org/abs/2312.12584)
9. [General Maximum-Cardinality Matching, Algorithms II, Dalhousie University](https://web.cs.dal.ca/~nzeh/Teaching/4113/book/matching/general_maximum_cardinality_matching/intro.html)
10. [First Mathematical Theory of Efficient Combinatorial Algorithms: Jack Edmonds, NIST](https://www.nist.gov/mathematics-statistics/first-mathematical-theory-efficient-combinatorial-algorithms-jack-edmonds)
11. [Chuzhoy, J. and Khanna, S. (2024). Maximum Bipartite Matching in n^{2+o(1)} Time via a Combinatorial Algorithm, arXiv](https://arxiv.org/abs/2405.20861)
12. [Improved average case analysis of the maximum cardinality matching problem, ALCOMFT-TR-03-111](https://www.cs.au.dk/~gerth/alcom-ft/TR/ALCOMFT-TR-03-111.html)
13. [Hegerfeld, F. and Kratsch, S. (2019). On adaptive algorithms for maximum matching, arXiv](https://arxiv.org/abs/1904.11244)
14. [Maximum matchings in general graphs through randomization, Journal of Algorithms (1989)](https://www.sciencedirect.com/science/article/pii/0196677489900059)
15. [Lecture notes on kidney exchange matching, IIT Bombay](https://www.cse.iitb.ac.in/~swaprava/courses/cs6002/scribed/lec03.pdf)
16. [Profile-based optimal matchings in the Student/Project Allocation problem, arXiv](https://arxiv.org/abs/1403.0751)
17. [Using Cardinality Matching to Design Balanced and Representative Samples for Observational Studies, arXiv](https://arxiv.org/abs/2201.04276)
18. [networkx.algorithms.matching source code, NetworkX 3.7 documentation](https://networkx.org/documentation/stable/_modules/networkx/algorithms/matching.html)
19. [nvlpubs.nist.gov](https://nvlpubs.nist.gov/nistpubs/sp958-lide/140-144.pdf)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Computational graph problems and algorithms › Matching algorithms*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license