Matching (graph theory)
A matching in a finite undirected graph (G=(V,E)) is a set (M\subseteq E) whose edges have no common endpoints. Equivalently, every vertex is incident with at most one edge of (M). A vertex incident with an edge of (M) is described as matched or saturated, whereas every remaining vertex is unmatched or exposed.
Matching theory concerns the existence, structure, enumeration, and computation of such edge sets. Its central results relate local conditions on neighborhoods and alternating paths to global statements about cardinality. The theory also provides fundamental connections among network flow, linear programming, polyhedral combinatorics, and the decomposition of graphs.
Fundamental definitions
The cardinality of a matching (M) is the number (|M|) of edges that it contains. A maximum matching is a matching of greatest possible cardinality, and its size is the matching number
[ \nu(G)=\max{|M|:M\text{ is a matching in }G}. ]
A maximal matching is instead one that is not properly contained in another matching. Every maximum matching is maximal, but a maximal matching need not be maximum. For example, the middle edge of a path on four vertices forms a maximal matching of size one, while the two terminal edges form a maximum matching of size two.
A perfect matching saturates every vertex. Consequently, a graph with a perfect matching has an even number of vertices and satisfies
[ \nu(G)=\frac{|V|}{2}. ]
A near-perfect matching leaves exactly one vertex unmatched. This notion is particularly relevant to factor-critical graph structure, in which deletion of any single vertex leaves a graph possessing a perfect matching.
Matchings may also carry numerical data. Given a weight function (w:E\to\mathbb{R}), the weight of (M) is
[ w(M)=\sum_{e\in M}w(e). ]
A maximum-weight matching maximizes this sum among all matchings under consideration. Maximum-cardinality matching and maximum-weight perfect matching are distinct optimization problems, although both admit polynomial-time algorithms for general graphs.
Alternating paths and the augmentation criterion
Let (M) be a matching. A path is (M)-alternating when its edges alternate between membership and nonmembership in (M). An augmenting path is an alternating path whose two endpoints are unmatched and whose first and last edges do not belong to (M).
If (P) is an augmenting path, the symmetric difference
[ M\mathbin{\triangle}E(P) ]
is another matching. It contains every matching edge outside (P), removes the matching edges on (P), and inserts the previously unused edges on (P). Since an augmenting path contains one more nonmatching edge than matching edge, this transformation increases the matching cardinality by one.
The converse is Berge's lemma: a matching is maximum if and only if no augmenting path exists relative to it. Claude Berge established this characterization in 1957. In a 1959 structural reformulation, You Watanabe expressed the comparison of two matchings through the connected components of their symmetric difference, separating alternating cycles from alternating paths and identifying the component responsible for augmentation. This componentwise form became a standard proof framework for the lemma.
For two matchings (M) and (N), every vertex has degree at most two in the graph with edge set (M\triangle N). Its nontrivial connected components are therefore alternating paths or even alternating cycles. If (|N|>|M|), at least one path component contains more edges of (N) than of (M), and that component is an augmenting path with respect to (M). This argument explains why the absence of augmentation is a complete optimality certificate rather than merely a local condition.
Bipartite matching
A bipartite graph has a vertex partition (V=X\cup Y) in which every edge joins a vertex of (X) to a vertex of (Y). Matchings in bipartite graphs possess especially direct characterizations because alternating searches cannot encounter odd cycles.
For (S\subseteq X), let (N(S)\subseteq Y) denote the set of vertices adjacent to at least one vertex of (S). Hall's marriage theorem, proved by Philip Hall in 1935, states that a matching saturating every vertex of (X) exists exactly when
[ |N(S)|\geq |S| \qquad\text{for every }S\subseteq X. ]
The necessity follows because the vertices of (S) require distinct matched neighbors. The sufficiency encodes the global effect of this condition and can be derived through augmenting paths, network flow, or induction.
When (|X|=|Y|), Hall's condition is equivalent to the existence of a perfect matching. For a (k)-regular bipartite graph with (k>0), edge counting between (S) and (N(S)) gives
[ k|S|\leq k|N(S)|, ]
so Hall's condition holds. Every regular bipartite graph of positive degree therefore has a perfect matching.
Bipartite matching is also linked to vertex covering. A vertex cover is a set of vertices incident with every edge, and its minimum possible size is denoted by (\tau(G)). Every matching and every vertex cover satisfy (|M|\leq |C|), since distinct matching edges require distinct covering incidences. Kőnig's theorem, established by Dénes Kőnig, states that equality holds for bipartite graphs:
[ \nu(G)=\tau(G). ]
This equality is an integral form of linear-programming duality. It generally fails outside the bipartite setting; a triangle, for example, has matching number one and minimum vertex-cover size two.
General graphs and blossoms
In a nonbipartite graph, an alternating search may encounter an odd cycle whose edges alternate except at a common base vertex. Such a configuration is called a blossom. Treating the cycle as an ordinary search-tree structure can conceal an augmenting path, because the parity of a route through the cycle depends on which direction around the odd cycle is used.
Jack Edmonds incorporated blossom contraction into a polynomial-time matching algorithm in 1965. An odd alternating cycle can be contracted to a single pseudovertex while preserving the existence or nonexistence of an augmenting path. An augmenting path in the contracted graph corresponds to one in the original graph after the contracted cycle is expanded with the parity-compatible route through the blossom.
The significance of contraction is structural as well as algorithmic. Odd cycles are the principal obstruction separating general matching from bipartite matching. Bipartite graphs contain no odd cycles, so their augmenting-path searches require no blossom operation. General graphs require additional inequalities and parity arguments for the same reason.
Edmonds's work also established matching as an early example of a combinatorial optimization problem whose polynomial-time solvability is not apparent from exhaustive search. Later algorithms refined the running time while retaining the alternating-path and blossom framework. For bipartite graphs, the Hopcroft–Karp algorithm computes a maximum matching in
[ O(|E|\sqrt{|V|}) ]
time by augmenting along collections of shortest vertex-disjoint augmenting paths. Comparable asymptotic bounds for general unweighted matching require a more elaborate treatment of nested blossoms.
Matching polytopes
Each matching (M) has an incidence vector (x^M\in{0,1}^{E}), where (x^M_e=1) exactly when (e\in M). The matching polytope is the convex hull of these incidence vectors.
For a bipartite graph, the polytope is described by nonnegativity and the degree constraints
[ x_e\geq 0 \qquad\text{for every }e\in E, ]
[ \sum_{e\in\delta(v)}x_e\leq 1 \qquad\text{for every }v\in V, ]
where (\delta(v)) is the set of edges incident with (v). The relevant constraint matrix is totally unimodular, so every extreme point of this linear system is integral.
For general graphs, the degree constraints alone admit fractional extreme points. Assigning (x_e=\tfrac12) to every edge of a triangle satisfies every degree constraint, although it is not a convex combination that behaves as an integral matching under the incomplete description. The missing restrictions are the odd-set inequalities
[ \sum_{e\in E(S)}x_e\leq \frac{|S|-1}{2} \qquad \text{for every odd }S\subseteq V, ]
where (E(S)) consists of the edges with both endpoints in (S). Edmonds proved that nonnegativity, degree constraints, and all odd-set inequalities describe the matching polytope of a general graph.
The exponentially large family of odd-set inequalities does not imply exponential computational complexity. A polynomial-time separation method can detect whether a proposed point violates one of these inequalities, connecting the polyhedral description with polynomial-time optimization through the equivalence of separation and optimization.
Decomposition and structural consequences
A perfect matching is also called a (1)-factor, and a decomposition of an edge set into perfect matchings is a 1-factorization. In a regular bipartite graph, repeated consequences of Hall's theorem yield a decomposition into perfect matchings. Thus, every (k)-regular bipartite graph can have its edge set partitioned into (k) disjoint perfect matchings.
This statement is equivalent to the edge-coloring result
[ \chi'(G)=\Delta(G) ]
for bipartite graphs, where (\chi'(G)) is the chromatic index and (\Delta(G)) is the maximum degree. Each color class is a matching, and in the regular case every color class saturates all vertices.
Perfect matchings also appear in the decomposition of doubly stochastic matrices. The Birkhoff–von Neumann theorem states that every doubly stochastic matrix is a convex combination of permutation matrices. Interpreting positive matrix entries as edges of a bipartite graph identifies permutation matrices with perfect matchings, thereby placing the theorem within the polyhedral structure of bipartite matching.