Matching (graph theory)

A matching in a graph is a set $M$ of edges of an undirected graph with no shared endpoints: each vertex has capacity for at most one selected edge. It describes simultaneous compatible pairs, such as jobs assigned to distinct available workers, or tasks each occupying two resources that cannot be shared. The empty set is a valid matching in a graph.^[ref]

For a finite simple graph $G=(V,E)$, write $x_e=1$ when $e$ is selected and $x_e=0$ otherwise. The vertex capacity constraint is exactlyThese are constraints on a discrete selection, not a requirement that every vertex be used. A matching in a graph with matching saturation of all vertices is a perfect matching; an unmatched vertex in a matching uses none of its capacity.

The objective must be specified separately. A maximum cardinality matching selects as many edges as possible; a maximum-weight matching selects the greatest total benefit; a minimum-weight perfect matching minimizes cost while requiring every vertex to be paired. A maximal matching only says that no additional edge fits alongside the current choices. The four-vertex path graph below separates these notions: choosing the middle edge blocks both outer edges, yet replacing it by those two edges pairs more vertices.

This model is useful because conflicts are local at vertices, while the quality of a selection can depend on coordinated changes along a whole augmenting path in a matching. A greedy matching gives a quick feasible selection; Berge's theorem explains when searching for such changes has reached a maximum cardinality matching. Repeating the pairing problem over time leads instead to proper edge colouring, where each time slot is a matching in a graph.

For the degree-constrained linear programming relaxation of a matching in a graph, retain precisely the edges with fractional coordinates. In a bipartite graph, an even graph cycle in this subgraph permits alternating positive and negative perturbations preserving all vertex sums. If the subgraph is a forest, use a graph path between two tree leaves: its endpoints have positive slack and its internal sums remain unchanged. Either perturbation expresses the original feasible point as the midpoint of two distinct feasible points. Hence a fractional feasible point cannot be an extreme point, proving integrality of all extreme points of the bipartite degree relaxation.

A matching in a graph on a rooted tree has the sibling-support condition if every unmatched non-root vertex has its parent matched to one of its siblings in a rooted tree. This is the properness condition used here. The root has no parent, so either exempt an unmatched root or require it to be matched in a nontrivial instance; the unmatched-vertex bound for a proper tree matching holds under either convention. Properness is stronger than being maximal: on the path $r-a-b-c$ rooted at $r$, selecting only $ab$ gives a maximal matching in a graph, but unmatched $c$ has parent $b$ matched upward rather than to a sibling of $c$.

For a proper matching in a rooted tree, the number of unmatched vertices in a matching does not exceed the number of leaves of a rooted tree. From each unmatched vertex, build a downward path: at an internal current node that is unmatched or matched upward, every child must be matched downward to one of its own children, or properness would fail. Follow a child and its matching partner, then repeat. The path terminates at a leaf and contains no other unmatched vertex. Two such downward paths cannot meet, since then one unmatched starting point would lie on the other's path. Their distinct endpoints give the required injection. No maximum-size assumption is needed.

For a bipartite graph with bipartition $L,R$ and nonnegative integer bounds $b_v$, a bipartite b-matching is an edge subset $F$ whose degree of a vertex is at most $b_v$ at each $v$. Taking $b_v=1$ gives a matching in a graph. To maximize $|F|$, build a flow network with arcs $s\to u$ of flow network edge capacity $b_u$ for $u\in L$, arcs $u\to v$ of flow network edge capacity one for $uv\in E$, and arcs $v\to t$ of flow network edge capacity $b_v$ for $v\in R$. The integral max-flow theorem gives an integral optimum. Select precisely the middle arcs with flow one. Flow conservation identifies their endpoint degrees with the outside arc flows, and the flow value is $|F|$. Conversely, every such edge subset supplies a feasible flow of that value. This proves the reduction and its optimality.

If a finite graph has no isolated vertex, its minimum edge cover cardinality $\rho (G)$ and matching number $\nu (G)$ sum to its number of vertices.

Proof. Start with a maximum cardinality matching $M$. Its unmatched vertices in a matching form an independent set, since an edge between two of them could be added. Add one incident edge for each such vertex. They are distinct, giving an edge cover of size $|M|+|V|-2|M|=|V|-\nu (G)$.

Conversely, in any inclusion-minimal edge cover $F$, every edge has an endpoint of vertex degree one in $(V,F)$; otherwise it could be removed. Thus each component is a star graph: two vertices of vertex degree at least two in one component would produce a graph path containing an edge with both endpoints of vertex degree at least two. If there are $t$ components, $|F|=|V|-t$. Selecting one edge from each star graph gives a matching in a graph of size $t$, so $\nu (G)\ge t$ and $|F|\ge |V|-\nu (G)$. A minimum-cardinality edge cover is inclusion-minimal, completing the proof. The constructive first half also gives a polynomial-time algorithm once a maximum cardinality matching is available.

A finite bipartite graph of positive maximum degree $\Delta$ has a matching in a graph covering every vertex of vertex degree $\Delta$. To cover the vertices of maximum degree in one side $A$, apply Hall's marriage theorem to that subset: for each subset $S$ of it, double counting gives $\Delta |S|\le \Delta |N(S)|$, where $N(S)$ is its graph neighbourhood. Construct the corresponding matching in a graph for the other side, then use the union of two matchings to cover both specified subsets simultaneously.

In the spanning subgraph formed by the union of two matchings in a graph $M_1,M_2$, every vertex has vertex degree at most two. A common edge is an isolated two-vertex connected component of a graph. Every other nontrivial connected component of a graph is a graph path or an even graph cycle, with the edges alternating between the two matchings in a graph.

Suppose the original graph is a bipartite graph with vertex sets $A,B$, $M_1$ covers a specified subset $X\subseteq A$, and $M_2$ covers a specified subset $Y\subseteq B$. Their union contains a matching in a graph covering $X\cup Y$. On an even graph cycle, either alternating choice covers every vertex. On an odd-length graph path, the larger alternating choice covers every vertex. On an even-length graph path, both endpoints lie in the same side: choose $M_1$ if they lie in $A$, or $M_2$ if they lie in $B$. Every required endpoint is covered by that choice, and every internal vertex meets both choices. Select each common edge as well; isolated vertices are not in $X\cup Y$. Different connected components of a graph do not interfere.

A vertex is an unmatched vertex in a matching $M$ if no edge of $M$ is incident to it. It is also called free or exposed, always relative to the specified matching in a graph: changing $M$ can change which vertices are free. The endpoints of an augmenting path in a matching must be distinct unmatched vertices in a matching before the change.

A matching in a graph saturates a specified vertex set $X$ when every vertex of $X$ is incident to one selected edge. Exactly one selected edge meets each such vertex, since matching edges have disjoint endpoints. Vertices outside $X$ may remain unmatched. A perfect matching saturates the entire vertex set; Hall's marriage theorem tests matching saturation of a specified side in a finite bipartite graph.

A stable matching in a bipartite graph pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite bipartite graph $G=(L\cup R,E)$ a strict preference ordering at each vertex over its neighbours of a vertex. An edge means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal cardinalities. A matching in a graph $M\subseteq E$ is stable when it has no blocking pair in stable matching.

Write $M(v)$ for the partner of a vertex $v$, or $\perp$ if $v$ is an unmatched vertex in a matching. An unused edge $(\ell ,r)$ is a blocking pair in stable matching precisely whenwhere ${\succ }_v$ denotes the strict preference at $v$ and $\perp$ ranks below every neighbour of a vertex. Both inequalities matter: wanting a different partner alone cannot upset a stable matching. A stable matching need not be a perfect matching; the Gale-Shapley algorithm still finds one with incomplete lists and unequal sides.

Here is an original example on the complete bipartite graph $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:There are two stable matchings,For $M_L$, the only unpaired partners preferred by left vertices are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a blocking pair in stable matching. For $M_R$, the left vertices want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right vertex prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.

By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a perfect matching with a blocking pair in stable matching $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused edge.

There are $3!=6$ permutations of right partners. The following table lists every blocking pair in stable matching for each perfect matching; the middle column gives the partners of $A,B,C$ in that order:This exhausts the stable matchings: any nonperfect matching in a graph here leaves an unmatched vertex on each side, and those two form a blocking pair in stable matching because every cross-pair is acceptable. Notice that every left vertex prefers $M_L$ and every right vertex prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.

A stable matching addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or maximum-weight matching objective. For example, assigning benefit $100$ to each edge of $N$ and zero to every other edge makes $N$ the unique maximum-weight matching, yet $(B,Y)$ still blocks it under the displayed preference relations. Such external benefits need not represent participants' rankings.

If the endpoints of an edge rank one another last and one stable matching in a bipartite graph contains that edge, every stable matching contains it. In the symmetric difference of two stable matchings, preference comparisons propagate along alternating paths: if a vertex prefers its new partner, that partner must prefer its old partner to avoid blocking the old matching. An alternating path cannot end unmatched on the preferred side, so the component is an alternating cycle, on which the two parts prefer opposite matchings. A mutual-worst edge absent from the new matching would make both its endpoints prefer the new matching, contradicting this propagation.

The Gale-Shapley algorithm constructs a stable matching by letting one side propose and the other hold its best offer so far. The word "deferred" is essential: a held proposal is tentative and can be replaced. David Gale and Lloyd Shapley presented this construction in their 1962 paper, College Admissions and the Stability of Marriage, §3, printed pp. 12–13; §4 extends it to college quotas and unacceptable pairs.

For the one-partner bipartite graph model, designate $L$ as proposers and $R$ as receivers:

Held proposers wait; only unmatched proposers act. A receiver can replace its held partner, whereas a proposer never tries the same edge twice. Isolated vertices simply remain unmatched. These rules also describe incomplete acceptable lists and unequal sides without adding fictitious acceptable partners.

For the preference lists under stable matching, choose available proposers in queue data structure order, initially $A,B,C$, adding rejected proposers at the end. The proposals are $A\to X$, $B\to X$, $C\to Y$, $B\to Y$, $C\to Z$. At the fourth proposal, $Y$ replaces its held $C$ by $B$ because $B{\succ }_{Y}C$. This frees $C$ to try $Z$, producing $M_L$.

Reverse the proposing side. Starting in the order $X,Y,Z$, the proposals are $X\to C$, $Y\to A$, $Z\to A$, $Z\to B$. Now $A$ rejects $Z$ because it already holds $Y$. The result is $M_R$. Thus the choice of proposing side can change the output even with strict preferences and complete lists.

Why does the procedure work? Each edge receives at most one proposal, so at most $|E|$ proposals occur. At all times, the held edges form a matching in a graph, and each receiver holds its favourite proposer among all proposals received. A receiver's held partner can only improve according to its strict preference. If a proposer prefers $r$ to its final partner, or ends unmatched while $r$ is acceptable, it must already have proposed to $r$. A rejection means $r$ then held someone better, and its final partner is at least as good. Such an edge cannot be a blocking pair in stable matching. This covers every possible blocking pair in stable matching, proving stability at termination.

With a queue data structure of unmatched proposers, a next-choice pointer for each list, and constant-time receiver-rank lookups, each proposal takes constant work. Using Big O notation, the time complexity is $O(|E|+|V|)$ including initialization, provided list construction and rank preprocessing also take $O(|E|+|V|)$. Edge-indexed ranks with cross-referenced list entries, or expected constant-time hash lookups, allow sparse storage proportional to $|E|+|V|$. Repeatedly scanning a receiver's preference list to compare offers would lose this bound. For complete lists with $n$ vertices per side, $|E|=n^2$ and the bound is $O(n^2)$. Initializing full $n\times n$ rank tables itself costs $\Theta (n^2)$ time and space, even when only a sparse set of pairs is acceptable.

The Gale-Shapley algorithm does more than establish existence: with strict preferences, its output is a proposer-optimal stable matching.^[ref] It is also a receiver-pessimal stable matching, as proved below. Both qualifications compare partners across stable matchings.

For fixed strict preferences, a proposer-optimal stable matching gives each proposer its best partner obtainable in any stable matching, with unmatched ranked last. The Gale-Shapley algorithm achieves all these individual optima simultaneously. In the worked example, $M_L$ gives $A,B,C$ partners ranked $1,2,2$, respectively; the alternative $M_R$ gives them ranks $2,3,3$.

Suppose a first rejection of a pair belonging to some stable matching $S$ occurs when $r$ rejects $\ell$ for ${\ell }^{\prime }$. Every partner ${\ell }^{\prime }$ prefers to $r$ has already rejected it, so none can be its partner in $S$. If $S(r)=\ell$, then ${\ell }^{\prime }$ prefers $r$ to $S({\ell }^{\prime })$, while $r$ prefers ${\ell }^{\prime }$ to $\ell$: a blocking pair in stable matching, a contradiction. Hence no rejected pair is stable, and each proposer receives its best stable partner. Under strict preferences this also makes the outcome independent of proposal order.

For fixed strict preferences, the same output of the Gale-Shapley algorithm gives each receiver its worst partner obtainable in any stable matching, treating unmatched as last. "Worst" is restricted to stable possibilities: a receiver might still receive its favourite acceptable partner if every stable matching assigns it that partner. Reversing the proposing side gives receivers their best stable partners instead.

For a short proof, let $M$ be a proposer-optimal stable matching and $S$ any other stable matching. If a receiver $r$ preferred $M(r)=\ell$ to $S(r)$, then proposer optimality would make $\ell$ prefer $r=M(\ell )$ to $S(\ell )$, since the partners differ and preferences are strict. The pair $(\ell ,r)$ would block $S$. Therefore no receiver prefers its partner in $M$ to its partner in $S$. In the worked example, right-side ranks in $M_L$ are $2,2,3$ for $X,Y,Z$, whereas $M_R$ gives them $1,1,2$. Neither outcome is universally best for both sides.

An acceptable unused edge whose endpoints both prefer each other to their partners in a matching in a graph, treating every acceptable partner as preferable to being unmatched. A stable matching has no such edge. In the worked example, $(B,Y)$ blocks $N$ even though $A$ already has its first choice.

In a graph with $2n$ vertices, a near-perfect matching in a graph has $n-1$ edges and exactly two unmatched vertices.

The coefficient $m_k$ counts matchings in a graph with $k$ edges. For a bipartite graph with $n$ vertices on each side, $m_n$ counts perfect matchings and equals the permanent of a matrix of its bipartite adjacency matrix. Positive activity $\lambda$ makes $Z_G$ the normalizing constant of the weighted matching Markov chain.

For $0<a\le b$, expand the expectation under the weighted matching Markov chain stationary weights to obtain the displayed identity. If the largest matching in a graph has $n$ edges and $b/a\le 1+1/n$, the observable lies in $[1,e]$. Its sample mean has controlled error by the Hoeffding inequality. A product of $J$ ratios, each estimated to relative accuracy $O(\epsilon /J)$, approximates the full ratio to relative accuracy $O(\epsilon )$.

An alternating path in a matching $M$ is a graph path whose successive edges alternate between membership in $M$ and membership outside $M$. Here graph paths have no repeated vertices. Alternation alone does not make a graph path an augmenting path in a matching: its endpoints must both be unmatched vertices in a matching. For example, relative to $M=\{(2,3),(4,5)\}$ in the six-vertex path graph, $2,3,4,5$ alternates but has matched endpoints; toggling just those three edges loses one selected edge.

An augmenting path in a matching $M$ is a nonempty alternating path in a matching with distinct endpoints that are both unmatched vertices in a matching. Its first and last edges lie outside $M$. Thus it has $k+1$ unselected edges and $k$ selected edges, for some $k\ge 0$. Taking the symmetric differenceremoves the selected edges on $P$ and inserts its unselected edges. Each internal vertex exchanges one selected edge for another; each endpoint gains its first selected edge. All choices away from $P$ stay in place, so $M^{\prime }$ is a matching in a graph with $|M^{\prime }|=|M|+1$.^[ref]

For an explicit repair, let the path graph $P_6$ have vertices $1,2,3,4,5,6$ in that order and start withThe endpoints $1$ and $6$ are initially unmatched vertices in a matching. Along $P$ the edges are outside, inside, outside, inside, outside $M$. Remove $(2,3)$ and $(4,5)$, then add $(1,2),(3,4),(5,6)$ together:This raises the cardinality from two to three and gives a perfect matching. Six vertices allow at most three disjoint pairs, so it is also a maximum cardinality matching. The initial $M$ is already a maximal matching: every unused edge touches a matched vertex. Augmentation succeeds because it can replace earlier choices instead of only adding to them.

One unused edge joining two unmatched vertices in a matching is the shortest possible augmenting path in a matching. Longer augmenting paths in a matching reassign several partners, explaining why a stalled greedy matching need not be optimal. For edge benefits $w_e$, the change in total benefit iswhich need not be positive even though the cardinality increases. A maximum-weight matching therefore needs a different optimality test. In an assignment equality graph an augmenting path in a matching moves toward a perfect matching while preserving zero reduced costs on matched edges; this is the setting used by the Hungarian algorithm.

For a finite simple graph $G$ and a matching in a graph $M\subseteq E(G)$, $M$ is a maximum cardinality matching if and only if $G$ has no augmenting path in a matching relative to $M$. The graph need not be a bipartite graph, and the assertion concerns cardinality, not edge benefits.^[ref]

The criterion turns a global comparison with every competing matching in a graph into a search for one repair. Starting from any matching in a graph, repeatedly find and toggle an augmenting path in a matching. Each step adds one selected edge, so finiteness gives termination after at most $\lfloor |V(G)|/2\rfloor -|M|$ steps; absence of any further augmenting path in a matching certifies maximum cardinality. This is an optimality criterion, not by itself a bound on the work needed to find each graph path.

For a short proof outline, an augmenting path in a matching immediately contradicts maximum cardinality. Conversely, if another matching in a graph $N$ has $|N|>|M|$, consider the subgraph whose set of edges is $M△N$. Its vertices have degree of a vertex at most two; its nontrivial connected components are graph paths and even cycles in a graph, alternating between the two matchings in a graph. A cycle in a graph contributes equal numbers from each. Hence some graph path contributes one more edge from $N$ than from $M$ and starts and ends with edges from $N$. Its endpoints are unmatched vertices in a matching relative to $M$, yielding the required augmenting path in a matching.

The two sides have $n$ vertices each. Given a nonperfect matching in a graph, choose unmatched vertices $u,v$ on opposite sides. An unmatched neighbour of either supplies a one-edge augmenting path in a matching. Otherwise their neighbours are matched; the matched left vertices corresponding to $N(u)$ and the set $N(v)$ have total size greater than $n$, so they intersect. This supplies the alternating path in a graph $u,b,a,v$ with $ab$ in the matching in a graph. Repeated augmentation produces a perfect matching.

Choose such an augmentation deterministically. Its reverse is specified by at most four vertices, giving at most $2n^4$ preimages for a matching in a graph of the next size. Thus the matching generating function coefficients satisfy $m_k\le 2n^4{m}_{k+1}$.

A perfect matching is a matching in a graph that covers every vertex exactly once. Its edges have no shared endpoints, and every vertex is an endpoint of one selected edge. It is useful when a collection must be divided into disjoint pairs with no element left over.

In a bipartite graph with equally many vertices on its two sides, a perfect matching can assign every person one allowed job and every job one person. The example under permanent of a matrix has three people and three jobs, with exactly three valid assignments. The blue edges below show those three perfect matchings; a crossing in the drawing is not an extra vertex.

Every selected edge covers two vertices, so a graph with an odd integer number of vertices has no perfect matching. An even integer number is necessary but does not guarantee existence: an isolated vertex cannot be covered. A perfect matching also need not be unique. For example, the complete bipartite graph $K_{2,2}$ has two perfect matchings, corresponding to the two ways of assigning two people to two jobs.

Counting all perfect matchings is a different question from finding one. For a zero-one biadjacency matrix of a balanced bipartite graph, the count is its permanent of a matrix. The nonzero determinant criterion for a perfect matching supplies an existence test, but cancellation means that a zero determinant does not rule one out.

A finite graph has a perfect matching if and only if the displayed inequalities hold, where $o(H)$ counts the connected components of a graph $H$ with an odd integer number of vertices. The theorem is associated with William Thomas Tutte.^[ref]

Necessity has a direct counting proof: each such component of $G-S$ must send at least one edge of a perfect matching to $S$, and different components must use different vertices of $S$. The sufficiency direction is the substantive content of the theorem. The criterion is useful because vertex degree and parity estimates can prove existence without constructing the perfect matching, as in the perfect matching theorem for a cubic graph with at most two bridges.

A vertex on one side of a balanced bipartite graph is flexible if every incident edge lies in a perfect matching. The strict Hall marriage theorem inequalities for nonempty proper subsets imply flexibility of every vertex: after forcing an edge, removal of its ends loses at most one neighbour from each remaining set. If a perfect matching exists without the strict condition, choose a minimal nonempty tight set. Its induced balanced graph has the strict condition internally, and each internal matching extends using the original matching outside that set. Thus at least one flexible vertex always exists.

A minimum-weight perfect matching pairs every vertex exactly once while minimizing total edge weight. General weighted perfect matching has polynomial-time algorithms. In the Christofides algorithm, it corrects precisely the odd-degree vertices of a minimum spanning tree. Alternating edges of a cyclic order on an even number of vertices give two perfect matchings; the cheaper one costs at most half that cycle's cost.

A one-factorization partitions every edge of a graph into perfect matchings. Each matching uses every vertex exactly once. A total of synthemes is precisely a one-factorization of the complete graph on six points.

A maximal matching is a matching in a graph to which no extra edge can be added while retaining all current selected edges. Equivalently, no edge joins two unmatched vertices in a matching; those vertices form an independent set. Every maximum cardinality matching is a maximal matching, but the converse fails.

Take the path graph $P_4$ with vertices $1,2,3,4$ and edges $(1,2),(2,3),(3,4)$. A greedy algorithm that first selects the middle edge produces $M=\{(2,3)\}$. Both remaining edges touch a matched vertex, so this size-one matching in a graph is maximal. Yet $N=\{(1,2),(3,4)\}$ has two edges. No matching in a graph on four vertices has more than two edges, so $N$ is a maximum cardinality matching. The two remaining free vertices of $M$, namely $1$ and $4$, are not adjacent; that does not prevent a longer augmenting path in a matching from joining them.

Maximality is useful as a quick stopping rule and a modest guarantee. For any maximal matching $M$ and maximum cardinality matching $N$ in a finite simple graph, every edge of $N$ touches an endpoint of an edge of $M$. Assign it to one such edge of $M$. Since $N$ has disjoint endpoints, each edge of $M$ receives at most two assignments, proving $|N|\le 2|M|$. The P₄ example reaches equality. Thus maximality guarantees at least half the largest cardinality, but says nothing comparable about arbitrary edge benefits. Its selected endpoints also form a vertex cover, as explained under vertex cover.

A greedy matching starts with the empty matching in a graph, scans all edges in some order, and selects an edge exactly when both endpoints are unmatched vertices in a matching. For a finite graph, a complete scan returns a maximal matching: a rejected edge had a matched endpoint, which stays matched thereafter. Stopping before all edges have been considered need not give maximality. Changing the order can change the result; on P₄, middle-first gives one pair, whereas outer-first gives two. A greedy algorithm of this form never revisits its choices, while an augmenting path in a matching does.

For a finite graph $G$, the matching number isIt is the cardinality of a maximum cardinality matching. The vertex capacity constraint gives $0\le \nu (G)\le \lfloor |V(G)|/2\rfloor$. The worked path graph examples have $\nu (P_4)=2$ and $\nu (P_6)=3$. A perfect matching reaches $|V(G)|/2$; the empty graph has matching number zero.

A maximum cardinality matching is a matching in a graph with as many edges as any matching in a graph of the same graph. It has cardinality $\nu (G)$, the matching number, and need not be unique or be a perfect matching. For example, any single edge of a triangle in a graph is a maximum cardinality matching, but leaves one vertex unmatched. Berge's theorem characterizes these optima by the absence of an augmenting path in a matching.

Assign each edge $e$ a real benefit $w_e$. A maximum-weight matching maximizes ${\sum }_{e\in M}{w}_e$ over all matchings in a graph $M$; the empty matching in a graph is allowed. Setting every $w_e=1$ recovers a maximum cardinality matching, but otherwise the objectives can disagree.

On the same path graph $P_4$, give the middle edge benefit $3$ and each outer edge benefit $1$. The matching in a graph $\{(2,3)\}$ has total benefit $3$, while the two-edge matching in a graph $\{(1,2),(3,4)\}$ has total benefit $2$. Thus the smaller choice is the unique maximum-weight matching. If instead the requirement is to find a maximum cardinality matching and then maximize benefit among those, the outer edges must be chosen. Requiring a perfect matching before optimizing cost is another distinct problem, covered by minimum-weight perfect matching. With negative benefits a maximum-weight matching can even be empty, so it need not be a maximal matching.

For a finite graph without an isolated vertex and with nonnegative edge weights, put $c_v={\min }_{e\ni v}w(e)$ and let $e_v$ attain this minimum. Define savings $p(uv)=c_u+c_v-w(uv)$ and baseline $B={\sum }_v{c}_v$. A maximum-weight matching $M$ with weights $p$, allowing arbitrary cardinality, gives a minimum-weight edge coverIt replaces separate cheapest coverage of two endpoints by a shared edge when doing so saves enough weight. Savings can be negative even though original costs are nonnegative; such edges need not be selected.

Proof. The construction covers all vertices. Duplicate selected edges are counted once, so nonnegative weights give $w(F_M)\le B-p(M)$. Take an optimal edge cover and delete redundant edges to make it inclusion-minimal without increasing cost. Its components are star graphs, by the argument for the edge cover and matching identity. Select one edge from each component to obtain a matching in a graph $N$. A component with center $a$, selected leaf $b$ and other leaves $L$ contributes $w(ab)+{\sum }_{v\in L}{c}_v$ to $B-p(N)$, at most its total edge weight since $c_v\le w(av)$. Thus $B-p(N)\le \mathrm{OPT}$. Maximizing $p$ giveswhich proves both the construction and the displayed identity, including zero-weight cases. One call to a general-graph maximum-weight matching polynomial-time algorithm suffices, together with linear-time preprocessing. Choosing a maximum cardinality matching under these modified weights would impose an unnecessary constraint and can spoil the reduction.^[ref]

For nonnegative weights on a finite graph, scan edges in nonincreasing weight order, selecting each when it shares no endpoint with an already selected edge. This greedy matching is a factor-two approximation algorithm for maximum-weight matching.

Proof. Charge each optimal edge to itself if selected, and otherwise to an earlier selected edge that blocked it. The receiving edge weighs at least as much. Each selected edge receives at most two charges, since its two endpoints each meet at most one optimal edge. Summing proves the bound. Sorting takes $O(|E|\log |E|)$ time, followed by a scan that records which vertices are used.

The factor is sharp even for strictly positive weights. On a four-vertex path graph with consecutive weights $1,1+\epsilon ,1$, where $0<\epsilon <1$, the greedy matching weighs $1+\epsilon$ and the optimal matching in a graph weighs two. Their ratio tends to two as $\epsilon \downarrow 0$. For infinitely many sizes, use $k$ disjoint copies with $\epsilon =1/k$, $k\ge 2$. This example isolates the obstruction: a locally attractive edge can block two compatible edges.

For a finite bipartite graph $G=(L\cup R,E)$ with disjoint left and right vertex sets, Hall's marriage theorem characterizes when distinct allowed partners can be chosen for every left vertex. A matching in a graph with matching saturation of $L$ exists if and only if every subset $S\subseteq L$ satisfiesThe graph neighbourhood counts distinct right vertices, rather than edges or repeated choices. This is the Hall condition. Its failure supplies a concrete Hall obstruction. Necessity follows because the chosen partners of $S$ are distinct members of $N_G(S)$; sufficiency is the surprising assertion that these collective counts rule out every obstacle.^[ref]

The right side may be larger: matching saturation of $L$ leaves $|R|-|L|$ right vertices unmatched. Only when $|L|=|R|$ does a matching in a graph saturating $L$ automatically become a perfect matching. For a specified subset $X\subseteq L$, apply the same criterion only to $S\subseteq X$, using the induced subgraph on $X\cup R$. The remaining left vertices need not be matched. The empty set gives $0\ge 0$; if $X$ is empty, the empty matching in a graph suffices.

Consider a scheduling model with three unit-duration jobs $a,b,c$ and four available slots $1,2,3,4$ on one machine. Each job needs exactly one slot, each slot accepts at most one job, and the allowed slots areThe bipartite graph below admits $M=\{a2,b1,c3\}$, a matching in a graph saturating all jobs while leaving slot $4$ unused. It is not a perfect matching of the seven-vertex graph. A greedy choice $a1$ initially blocks $b$, but the augmenting path in a matching $b,1,a,2$ replaces $a1$ by $b1,a2$; subsequent assignment of $c3$ succeeds. A bad partial choice is not an impossibility certificate.

There are eight subsets of $L=\{a,b,c\}$. Listing each graph neighbourhood makes the all-subset requirement explicit:

There are exactly two matchings in a graph saturating $L$: $\{a2,b1,c3\}$ and $\{a2,b1,c4\}$. Job $b$ forces slot $1$, then job $a$ forces slot $2$, leaving two choices for $c$.

The Hall condition requires enough distinct neighbours for every subset of the specified left vertex set in a finite bipartite graph. Checking the whole left set establishes only one inequality. Checking singleton sets establishes only that each left vertex has positive degree of a vertex. Overlapping lists can pass both tests and still fail to admit matching saturation of the left side.

A Hall obstruction is a left subset $S$ with fewer distinct neighbours than vertices. At most $|N(S)|$ members of $S$ can be matched, so at least $|S|-|N(S)|$ must remain unmatched. The pigeonhole principle proves failure without enumerating every proposed assignment.

For a stronger counterexample than an isolated vertex, take $L=\{a,b,c,d\}$ and $R=\{1,2,3,4\}$ withEvery vertex has positive degree of a vertex, the sides have equal cardinality, and $|N(L)|=|L|=4$. Every two-vertex left subset also passes the Hall condition. Nevertheless $S=\{a,b,c\}$ has only $N(S)=\{1,2\}$, so $2<3$ rules out matching saturation of $L$.

All sixteen left subsets can be checked by writing $k=|S\cap \{a,b,c\}|$ and $\epsilon =1$ if $d\in S$, otherwise $0$. ThenOnly $k=3,\epsilon =0$ violates the Hall condition. Every matching in a graph uses at most two edges incident to $\{a,b,c\}$ and at most one incident to $d$, so the matching number is three. There are exactly twelve size-three matchings in a graph: choose two of $a,b,c$ in three ways, assign them to $1,2$ in two ways, and choose $3$ or $4$ for $d$. Thus the obstruction identifies the bottleneck: adding availability only for $d$ cannot help; allowing $c$ to use slot $3$ permits $\{a1,b2,c3,d4\}$, a perfect matching.

In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.

The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.

The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.

A system of distinct representatives for a finite indexed family of finite sets $(A_i{)}_{i\in I}$ chooses one element $x_i\in A_i$ per index, with all choices distinct. Form a bipartite graph with left vertex set $I$, right vertex set ${\bigcup }_{i\in I}{A}_i$, and edges $ix$ whenever $x\in A_i$. Matching saturation of $I$ is precisely a system of distinct representatives. Hence Hall's marriage theorem says that such choices exist exactly when $|{\bigcup }_{i\in J}{A}_i|\ge |J|$ for every subset $J\subseteq I$. Repeated equal sets still have separate indices and separate demands.

For sufficiency, take a matching in a graph of maximum size and suppose a left vertex $u$ is unmatched. Follow unused edges from left to right and matching edges back to the left. An unmatched reachable right vertex yields an augmenting path in a matching, contradicting maximal size. Otherwise let $S,T$ be the reachable left and right sets. Every member of $T$ is matched to a distinct member of $S\setminus \{u\}$, and every member of $S\setminus \{u\}$ is reached this way. Since $N(S)=T$, we obtain $|N(S)|=|S|-1$, contradicting the Hall condition. Finiteness ensures that a maximum-size matching in a graph exists.

The alternative Hall induction through a tight set uses mathematical induction: a proper nonempty subset with $|N(S)|=|S|$ splits off a balanced induced subgraph; without such a tight set, deleting one chosen edge's endpoints preserves the Hall condition on the smaller left side.

In the equal-part random bipartite graph with fixed edge probability $0<p<1$, rule out empty rectangles of side $\lceil \sqrt{n}\rceil$ and vertices with at least $n-\lceil \sqrt{n}\rceil$ nonneighbors. A union bound gives the displayed asymptotic estimate. Small vertex sets satisfy Hall's condition by the degree bound; intermediate sets do so because their omitted-neighbor rectangle would contain a forbidden square; large sets meet every vertex in the other part. Thus Hall's marriage theorem gives a perfect matching asymptotically almost surely. This does not mean probability one at any finite size.

Two maximum-cardinality $\epsilon$-separated subsets $A,B$ of a compact metric space have a bijection that moves each point by less than $\epsilon$. Join $a$ to $b$ when their distance is below $\epsilon$. If $S\subseteq A$ had fewer than $|S|$ neighbours, replacing these neighbours in $B$ by $S$ would create a larger separated set. The Hall marriage theorem therefore supplies a perfect matching. This allows empirical averages on a compact isometry group to be made approximately invariant without assuming a prior Haar measure construction.

In a finite bipartite graph, suppose every left vertex has positive degree and each edge joins vertices with $d(x)\ge d(y)$ from left to right. Then $|N(A)|\ge {\sum }_{x\in A}{\sum }_{y\sim x}1/d(y)\ge |A|$, so a matching covers the left side.

For finitely many Lebesgue measurable sets $A_i\subseteq [0,1]$ and nonnegative demands $b_i$, pairwise disjoint measurable subsets $B_i\subseteq A_i$ with $\lambda (B_i)=b_i$ exist exactly when $\lambda ({\bigcup }_{i\in I}{A}_i)\ge {\sum }_{i\in I}{b}_i$ for every index subset $I$. Necessity is additivity and monotonicity of Lebesgue measure. For sufficiency, partition the set union into membership cells $E_J$, send flow from a source through demand vertices $i$ to cells with $i\in J$, then to a sink. Source capacities are $b_i$, cell capacities are $\lambda (E_J)$, and intermediate capacities are $D={\sum }_i{b}_i$. Every cut of a flow network has capacity at least $D$ by the assumed inequalities. The max-flow min-cut theorem provides the allocations, and divisibility of Lebesgue measure turns each cell allocation into disjoint pieces. If $D=0$, all $B_i$ can simply be empty.

For Hall's theorem, either every proper nonempty set has one excess neighbour and one deletes an arbitrary edge's endpoints, or a tight set $S$ with $|N(S)|=|S|$ splits the problem into the induced graph on $S\cup N(S)$ and its complement.

In a $k$-regular bipartite graph, edge counting gives equal vertex-class sizes and $k|S|\le k|N(S)|$. Hall's theorem therefore supplies a perfect matching.

If a $k$-regular graph on $n$ vertices has a maximum matching of size $m$, its unmatched vertices are independent. Counting their incident edges gives $k(n-2m)\le 2(k-1)m$, and hence $m\ge kn/(4k-2)$.

The disjoint union of $r$ triangles is $2$-regular on $3r$ vertices and has matching number $r$, attaining the regular-graph lower bound $n/3$.