Matching in a graph

A matching is a set of edges with no shared endpoints. It saturates a vertex set when every vertex in that set is incident to one of its edges.

An augmenting path alternates between edges outside and inside a matching in a graph and joins two unmatched endpoints. Flipping its edges increases the matching size by one. In an assignment equality graph it moves toward a perfect matching while preserving zero reduced costs on matched edges.

A perfect matching saturates every vertex of the graph.

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 matching is maximal when no edge can be added to it, and maximum when no matching has more edges. Every maximum matching is maximal, and the unmatched vertices of a maximal matching form an independent set.

The matching number $\nu (G)$ is the largest number of edges in a matching of $G$.

A bipartite graph has a matching saturating $X$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq X$.

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$.