Assignment problem Created 2026-10-06 Updated 2026-10-14
The assignment problem chooses a one-to-one pairing of jobs and agents minimizing their total cost. Its minimum-cost flow formulation puts unit supplies on job vertices and unit demands on agent vertices of a bipartite graph. Integral feasible flows are perfect matchings.
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 difference
removes 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]
For an explicit repair, let the path graph have vertices in that order and start with
The 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.
Figure 1.
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 is
which 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 doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With initially positive entries, there are at most terms, since a positive-mass residual has at least positive entries. Elementary augmenting-path matching gives arithmetic operations.
An -regular graph with and a bridge in a graph separating an odd number of vertices from the rest cannot have an -colour proper edge colouring. Such a colouring would partition the edges into perfect matchings. Each perfect matching must cross the odd-sided cut of a graph, so each would have to contain its unique crossing edge, the bridge in a graph. An edge cannot belong to two colour classes.
For odd , every bridge in a graph in an -regular graph automatically has odd-sized sides: if is either resulting connected component of a graph, double counting gives , so parity forces odd. Thus an odd- regular graph with a bridge in a graph is a class two regular graph.
Class two regular graph 2026-10-25
An -regular graph is class two when its edge chromatic number exceeds . For a finite simple graph, Vizing's theorem makes that edge chromatic number exactly . An -colour proper edge colouring of an -regular graph would partition its edges into perfect matchings, since every vertex would see each colour exactly once.
Configuration model Created 2026-10-14 Updated 2026-10-20
For a prescribed degree sequence with even sum , attach labelled half-edges to vertex and choose a uniform perfect matching of the half-edges. Each pair becomes an edge, giving a multigraph that may have self-loops or parallel edges. The number of pairings is . Every simple graph with that degree sequence has exactly pairing representations, so conditioning on simplicity produces the uniform simple-graph model.
Counting complexity Created 2026-09-28 Updated 2026-11-05
Counting complexity studies the computational resources needed to count solutions. For a polynomial time decidable binary relation and a polynomial , a standard counting function is
The complexity class consists of these functions, equivalently the numbers of accepting computations of Nondeterministic Turing machines running in polynomial time. The witness encoding matters: counting computation paths and counting distinct outputs can give different answers.
For the propositional formula , the satisfying Boolean valuations are , and , so the answer is three. The associated decision problem asks only whether that count is positive. For a zero-one matrix, the permanent of a matrix counts perfect matchings in a bipartite graph. Testing whether any such perfect matching exists admits a polynomial-time algorithm, while counting them is -complete under polynomial-time Turing reductions.[ref]
Domino tiling 2026-11-05
A domino tiling covers a region made of unit squares by nonoverlapping rectangles, each occupying two adjacent squares. Equivalently, it is a perfect matching in the graph whose vertices are squares and whose edges join squares sharing a side. This translates a geometric covering problem into graph theory.
A rectangle has tilings satisfying , with . At the left edge, either one vertical domino leaves a rectangle, or two horizontal dominoes leave a rectangle. Hence , and . A checkerboard colouring gives a different tool: every domino covers one square of each colour, so unequal colour counts obstruct a tiling. Equal counts are necessary but need not suffice for arbitrary regions.
Flexible vertex in a balanced bipartite graph Created 2026-10-14 Updated 2026-10-25
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.
Two maximum-cardinality -separated subsets of a compact metric space have a bijection that moves each point by less than . Join to when their distance is below . If had fewer than neighbours, replacing these neighbours in by 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.
Hall obstruction 2026-10-14
A Hall obstruction is a left subset with fewer distinct neighbours than vertices. At most members of can be matched, so at least must remain unmatched. The pigeonhole principle proves failure without enumerating every proposed assignment.
For a stronger counterexample than an isolated vertex, take and with
Every vertex has positive degree of a vertex, the sides have equal cardinality, and . Every two-vertex left subset also passes the Hall condition. Nevertheless has only , so rules out matching saturation of .
Figure 1.
A three-vertex Hall obstruction has only two neighbours, despite enough slots in total
. Red boundaries identify and . Thick blue edges give the maximum-size matching in a graph ; and slot are unmatched. Details.
All sixteen left subsets can be checked by writing and if , otherwise . Then
Only violates the Hall condition. Every matching in a graph uses at most two edges incident to and at most one incident to , so the matching number is three. There are exactly twelve size-three matchings in a graph: choose two of in three ways, assign them to in two ways, and choose or for . Thus the obstruction identifies the bottleneck: adding availability only for cannot help; allowing to use slot permits , a perfect matching.
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 satisfies
The 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 are
The 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.
Figure 1.
A matching in a graph saturates all three jobs and leaves one of four slots unused
. Thick blue edges are ; thin grey edges are other allowed assignments. Crossings are not vertices. Details.
There are eight subsets of . Listing each graph neighbourhood makes the all-subset requirement explicit:
00
12
11
13
22
24
24
34
There are exactly two matchings in a graph saturating : and . Job forces slot , then job forces slot , leaving two choices for .
Hungarian algorithm Created 2026-10-06 Updated 2026-10-14
The Hungarian algorithm maintains feasible assignment dual potentials and a matching of equality edges. If the alternating search cannot augment, adjust reachable job and agent potentials by the smallest reduced cost leaving the search set. This preserves feasibility and existing matching equalities while exposing a new equality edge. A resulting perfect matching attains the dual lower bound.
Leslie G. Valiant 2026-11-05
Leslie G. Valiant proved in 1979 that computing the permanent of a zero-one matrix is complete for the counting complexity class under the paper's arithmetic reductions.[ref]
For a bipartite graph's zero-one adjacency matrix, the permanent counts perfect matchings. Deciding whether one exists admits a polynomial-time algorithm, while counting all of them has the paper's much stronger completeness property. This makes the difference between existence and counting concrete. The permanent resembles the determinant but lacks its alternating signs, so an efficient determinant algorithm does not automatically compute it. Valiant's permanent reduction encodes logical constraints into weighted combinatorial choices.
The coefficient counts matchings in a graph with edges. For a bipartite graph with vertices on each side, counts perfect matchings and equals the permanent of a matrix of its bipartite adjacency matrix. Positive activity makes the normalizing constant of the weighted matching Markov chain.
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]
For a finite simple graph , write when is selected and otherwise. The vertex capacity constraint is exactly
These 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.
Matching number Created 2026-09-24 Updated 2026-10-14
For a finite graph , the matching number is
It is the cardinality of a maximum cardinality matching. The vertex capacity constraint gives . The worked path graph examples have and . A perfect matching reaches ; the empty graph has matching number zero.
Matching saturation 2026-10-14
A matching in a graph saturates a specified vertex set when every vertex of is incident to one selected edge. Exactly one selected edge meets each such vertex, since matching edges have disjoint endpoints. Vertices outside 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 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.