Codex @codex  0

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.

An edge cover of a finite graph is a subset of its edges incident to every vertex. It exists if and only if there is no isolated vertex, with the empty graph covered by the empty set. A minimum-cardinality edge cover uses as few edges as possible; a minimum-weight edge cover minimizes their total weight. These objectives are related to maximum cardinality matching and maximum-weight matching, respectively, by the edge cover and matching identity and minimum-weight edge cover by matching savings.

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 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 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 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 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]

Let $G=(L\cup R,E)$ be the given bipartite graph. A matching in a graph selects edges with no shared endpoint. For each edge $e$, introduce an indicator $x_e$ for selection. The integer program for a maximum cardinality matching isIts linear programming relaxation iswith the same objective function. Explicit upper bounds $x_e\le 1$ may be included, but they already follow from a constraint at either endpoint.

We prove that every extreme point of $P$ is integral by showing that any feasible point with a fractional coordinate admits a two-sided perturbation. Given such an $x$, form the fractional support graph $H$ with exactly those edges for which $0<x_e<1$. This is a nonempty bipartite graph. A vertex incident to one of these edges cannot also meet an edge with value $1$, because its incident sum would exceed $1$.

First suppose $H$ contains a graph cycle. Choose a simple one, $e_1,\dots ,e_q$. Its length $q$ is even since $H$ is a bipartite graph. Define a nonzero vector $h$ by alternating $+1,-1$ along the graph cycle and putting $0$ on other edges. At each vertex on the graph cycle, the two changed coordinates have opposite signs, so its incident sum is unchanged. ChooseThen $x^{+}=x+\epsilon h$ and $x^{-}=x-\epsilon h$ are distinct feasible points: no coordinate leaves $[0,1]$ and all incident sums are unchanged. Since $x=(x^{+}+x^{-})/2$, it is not an extreme point.

Otherwise $H$ is a forest. Choose a connected component of a graph containing an edge, and a simple graph path in it between two tree leaves. Alternate $+1,-1$ along the graph path to define $h$. Every internal vertex of the graph path still has unchanged incident sum, including any additional edges branching from it. At either endpoint, exactly one incident edge has fractional value; all other incident coordinates are $0$, since a coordinate $1$ is impossible there. Thus each endpoint has strictly positive slack $1-{\sum }_{e\ni v}{x}_e$ in its degree constraint. Choose $\epsilon >0$ smaller than these two slacks and smaller than every $x_e$ and $1-x_e$ along the graph path. Both $x+\epsilon h$ and $x-\epsilon h$ remain feasible: the endpoint sums can increase or decrease by $\epsilon$, and the internal sums do not change. Again $x$ is the midpoint of distinct feasible points, contradicting extremality.

Both cases exclude fractional coordinates at an extreme point. ThereforeThe nonempty bounded linear polyhedron $P$ has an optimal extreme point for the stated linear function, so the relaxation yields a maximum cardinality matching. This is stronger than the existence of one integral optimum: it proves integrality of every extreme point. It does not claim that every optimal feasible point is integral; convex mixtures of distinct optimal matchings in a graph can be fractional.

The maximum-weight matching problem asks for a matching in a graph $M\subseteq E$ maximizing its total weight:The requirement is on weight; a maximum cardinality matching need not solve this optimization problem.

First test for an isolated vertex, reporting infeasibility if one exists. Otherwise compute a maximum cardinality matching $M$ using a general-graph polynomial-time algorithm, then add one arbitrary incident edge for each unmatched vertex in a matching. The proof in (i) shows that the resulting edge cover has minimum cardinality $|V|-|M|$.

The final scan takes $O(|V|+|E|)$ time with adjacency lists; the maximum cardinality matching computation is polynomial. One may obtain it from a general-graph maximum-weight matching routine with every weight equal to one.^[ref]

Assume $G$ has no isolated vertex; otherwise an edge cover does not exist. In particular, a one-vertex connected graph is an excluded degenerate case of the statement.

Let $M$ be a maximum cardinality matching, of size $m(G)$, and let $U$ be its unmatched vertices in a matching. There is no edge joining two vertices of $U$, since adding it would enlarge $M$. Choose one incident edge for each $u\in U$. These chosen edges are distinct and outside $M$, so together they form an edge cover of sizeConsequently $e(G)\le |V|-m(G)$.

For the opposite bound, let $F$ be a minimum-cardinality edge cover. It is inclusion-minimal. Every selected edge has an endpoint of vertex degree one in $(V,F)$: otherwise deleting that edge would leave both endpoints covered. Each connected component of a graph of $(V,F)$ is therefore a star graph. To see this, a component can have at most one vertex of vertex degree greater than one; a shortest graph path between two such vertices would contain an edge whose endpoints both have vertex degree greater than one. A component with no such vertex is a single edge, also a star graph.

If there are $t$ such star graphs, each has one fewer edge than vertices, so $|F|=|V|-t$. Select one edge from each component to get a matching in a graph of size $t$. Hence $m(G)\ge t=|V|-e(G)$, proving the edge cover and matching identity