Alternating path in a matching 2026-10-14
An alternating path in a matching is a graph path whose successive edges alternate between membership in and membership outside . 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 in the six-vertex path graph, alternates but has matched endpoints; toggling just those three edges loses one selected edge.
Augmenting path in a matching Created 2026-10-06 Updated 2026-10-14
An augmenting path in a matching 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 . Thus it has unselected edges and selected edges, for some . Taking the symmetric differenceremoves the selected edges on 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 stay in place, so is a matching in a graph with .[ref]
Graph Theory by Reinhard Diestel. Matching, Covering and Packing, §2.1, printed p. 2: alternating paths, augmenting paths and symmetric difference
For an explicit repair, let the path graph have vertices in that order and start withThe endpoints and are initially unmatched vertices in a matching. Along the edges are outside, inside, outside, inside, outside . Remove and , then add 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 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.
The augmenting path in a matching on P₆ replaces two selected edges by three using symmetric difference
. Details. 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 , 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.
Berge's theorem 2026-10-14
For a finite simple graph and a matching in a graph , is a maximum cardinality matching if and only if has no augmenting path in a matching relative to . The graph need not be a bipartite graph, and the assertion concerns cardinality, not edge benefits.[ref]
Two theorems in graph theory by Claude Berge. Claude Berge, Two theorems in graph theory, printed p. 842: finite unoriented graph and Problem 3; printed p. 843, Theorem 1: maximum matching and absence of an alternating chain between neutral points
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 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 has , consider the subgraph whose set of edges is . 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 than from and starts and ends with edges from . Its endpoints are unmatched vertices in a matching relative to , yielding the required augmenting path in a matching.
Greedy matching 2026-10-14
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.
Hall's marriage theorem Created 2026-10-14 Updated 2026-10-14
For a finite bipartite graph 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 exists if and only if every subset 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 are distinct members of ; sufficiency is the surprising assertion that these collective counts rule out every obstacle.[ref]
The right side may be larger: matching saturation of leaves right vertices unmatched. Only when does a matching in a graph saturating automatically become a perfect matching. For a specified subset , apply the same criterion only to , using the induced subgraph on . The remaining left vertices need not be matched. The empty set gives ; if is empty, the empty matching in a graph suffices.
Consider a scheduling model with three unit-duration jobs and four available slots 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 , a matching in a graph saturating all jobs while leaving slot unused. It is not a perfect matching of the seven-vertex graph. A greedy choice initially blocks , but the augmenting path in a matching replaces by ; subsequent assignment of succeeds. A bad partial choice is not an impossibility certificate.
There are eight subsets of . Listing each graph neighbourhood makes the all-subset requirement explicit:
There are exactly two matchings in a graph saturating : and . Job forces slot , then job forces slot , leaving two choices for .
Hall theorem proof outline 2026-10-14
For sufficiency, take a matching in a graph of maximum size and suppose a left vertex 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 be the reachable left and right sets. Every member of is matched to a distinct member of , and every member of is reached this way. Since , we obtain , 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 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.
Matching (graph theory) Created 2026-10-14 Updated 2026-10-31
A matching in a graph is a set 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]
Graph Theory by Reinhard Diestel. Matching, Covering and Packing, opening paragraph, printed p. 1: independent edges and matchings
For a finite simple graph , write when is selected and 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.
Maximal matching Created 2026-09-24 Updated 2026-10-14
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 with vertices and edges . A greedy algorithm that first selects the middle edge produces . Both remaining edges touch a matched vertex, so this size-one matching in a graph is maximal. Yet has two edges. No matching in a graph on four vertices has more than two edges, so is a maximum cardinality matching. The two remaining free vertices of , namely and , are not adjacent; that does not prevent a longer augmenting path in a matching from joining them.
Choosing the middle edge of P₄ gives a maximal matching of size one; the outer edges give a maximum cardinality matching of size two
. Details. Maximality is useful as a quick stopping rule and a modest guarantee. For any maximal matching and maximum cardinality matching in a finite simple graph, every edge of touches an endpoint of an edge of . Assign it to one such edge of . Since has disjoint endpoints, each edge of receives at most two assignments, proving . 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.
Maximum cardinality matching 2026-10-14
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 , 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.
Past exam of the mathematics course of the University of Cambridge 2011 ii Paper 1 17F Solution Created 2026-09-24 Updated 2026-10-14
A matching in a graph is a set of edges with no shared endpoints. A matching from to here covers every vertex of . Necessity of the Hall marriage theorem condition is immediate: the partners of vertices of are distinct members of its neighbour set .
For sufficiency, take a matching of maximum size. If it leaves unmatched, follow alternating unmatched and matched edges from . Let and be the reachable vertices. No vertex of can be unmatched, because the resulting augmenting path in a matching would increase the matching. Every neighbour of is in , and the matching pairs bijectively with . Thus , contradicting Hall's condition. The maximum matching therefore covers .
For the deficiency bound, adjoin new vertices to , each adjacent to all of . Every nonempty then has neighbours. Apply the Hall marriage theorem and remove the at most edges using new vertices. This leaves at least independent edges. The lower bound is vacuous if .
Write the adjacency matrix of a graph in bipartite block form . If Hall's condition failed for , the linear map from vectors supported on to their neighbour coordinates in would have fewer output than input coordinates. It therefore has a nonzero kernel, giving a nonzero vector supported on with . The vector would be a zero eigenvector of the adjacency matrix. Consequently absence of the zero eigenvalue implies a matching covering .
The converse is false, even with equal part sizes. The four-cycle has a perfect matching, but its matrix is singular. Its adjacency matrix has eigenvalues .
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 38 5 c Solution Created 2026-10-03 Updated 2026-10-06
For an explicit algorithm, keep an unnormalized residual , initially , whose row and column sums all equal a common mass , initially one. While , find a perfect matching in its positive support, form its permutation matrix , and subtract , where is the smallest selected entry. Record and replace by .
If the residual mass is positive, the same proof of the Hall marriage theorem condition applies after division by . Every subtraction removes at least one positive entry and creates no new positive entries. Before the last subtraction, any positive-mass residual has at least positive entries; the last step removes all its entries. If is the initial number of positive entries, thenSince the residual ultimately vanishes, summing the recorded subtractions gives , and the row sums give .
A perfect matching can be found by at most searches for an augmenting path in a matching, each costing in a graph with at most edges. Thus each iteration costs , including forming the support and updating the residual, and there are iterations. HenceThis bound uses exact real arithmetic. For rational input, a common denominator lets all residual subtractions be performed on integers of polynomial bit length, giving a polynomial bit-time implementation as well.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 212 3 Solution Created 2026-10-03 Updated 2026-10-06
Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply and agent vertices demand . An arc from job to agent has cost and nonnegative flow ; an upper bound may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its positive arcs form a perfect matching, hence give one job per agent.
A network simplex algorithm basis for this connected -vertex network has tree arcs, whereas an integral assignment has only positive flows. For , at least basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.
Suppose the assignment dual potentials satisfy . For every feasible assignment ,If the selected assignment uses only arcs with , its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by ; the TeX aid mistakenly replaces it with .
The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where . Search for an augmenting path in a matching in this equality graph. If there is none, let be the reachable jobs and the reachable agents in the alternating search from unmatched jobs. Every agent in is matched to a job in . SetReduced costs from to its complement decrease by , those from outside into increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.
For the example, start with the row minima and . The reduced cost matrix isMatch job to agent . Searching from both unmatched jobs gives and ; the minimum cost to an agent outside is . Update to and :The new equality edge augments the matching. From unmatched job , the next alternating search reaches agent and its matched job , giving and . Now . The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching uses job to agent , the reversed matched edge to job , then the new edge to agent . It gives the optimal assignmentThe dual linear program value is , an independent optimality certificate.
Short augmenting paths in a dense bipartite graph Created 2026-10-14 Updated 2026-10-14
The two sides have vertices each. Given a nonperfect matching in a graph, choose unmatched vertices 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 and the set have total size greater than , so they intersect. This supplies the alternating path in a graph with 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 preimages for a matching in a graph of the next size. Thus the matching generating function coefficients satisfy .
Unmatched vertex in a matching Created 2026-10-14 Updated 2026-10-25
A vertex is an unmatched vertex in a matching if no edge of is incident to it. It is also called free or exposed, always relative to the specified matching in a graph: changing 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.


