Let \(G\) be a finite simple graph and let \(M\) be a matching in \(G\). Then \(M\) is a maximum matching if and only if \(G\) contains no \(M\)-augmenting path.

Let \(G\) be a finite simple graph whose vertex set admits a bipartition into parts \(X\) and \(Y\), so that every edge of \(G\) joins a vertex of \(X\) to a vertex of \(Y\). For a set \(S\) of vertices write \(N(S) = \bigcup _{v \in S} N(v)\) for the union of the neighborhoods of the vertices in \(S\). Then \(G\) has a matching that saturates \(X\) — a set of pairwise disjoint edges covering every vertex of \(X\) — if and only if \(\left\lvert S\right\rvert \le \left\lvert N(S)\right\rvert \) for every \(S \subseteq X\).

Let \(G\) be a simple graph on a finite vertex set that is bipartite with parts \(X\) and \(Y\), so that every edge of \(G\) joins a vertex of \(X\) to a vertex of \(Y\). If there is an integer \(k \gt 0\) such that every vertex of \(G\) has degree exactly \(k\), then \(G\) admits a perfect matching: a set of edges that is vertex-disjoint and covers every vertex of \(G\).

Let \(G\) be a finite simple graph. If \(M\) is a matching in \(G\) and \(K\) is a covering of \(G\), then the number of edges of \(M\) is at most the number of vertices in \(K\); that is, \(\left\lvert M\right\rvert \le \left\lvert K\right\rvert \).

Let \(G\) be a finite simple graph, let \(M\) be a matching in \(G\), and let \(K\) be a covering of \(G\). If \(|M| = |K|\), then \(M\) is a maximum matching and \(K\) is a minimum covering of \(G\).

Let \(G\) be a finite bipartite graph with bipartition \((X, Y)\) of its vertex set. If \(M\) is a maximum matching of \(G\) and \(K\) is a minimum covering of \(G\), then the number of edges in \(M\) equals the number of vertices in \(K\).

Let \(G\) be a simple graph on a finite vertex set \(V\). For a set \(S \subseteq V\), write \(G - S\) for the graph obtained by deleting the vertices of \(S\) (together with their incident edges), and let \(o(G - S)\) denote the number of odd components of \(G - S\), that is, the connected components with an odd number of vertices. Then \(G\) has a perfect matching if and only if

Let \(G\) be a finite simple graph that is \(3\)-regular (every vertex has exactly three neighbours) and bridgeless (no edge of \(G\) is a bridge, i.e. removing any single edge leaves the graph with the same number of connected components). Then \(G\) has a perfect matching: there is a set of edges, no two sharing a vertex, that together cover every vertex of \(G\).

Let \(G\) be a bipartite graph on a finite vertex set with bipartition into parts \(X\) and \(Y\) whose union is the whole vertex set, and let \(w\) assign a real weight to each edge. Suppose \(l\) is a feasible vertex labelling for these weights, and let \(G_l\) be the corresponding equality subgraph. If \(G_l\) contains a perfect matching \(M^*\), then \(M^*\), regarded as a matching of \(G\), is an optimal matching of \(G\) — that is, a perfect matching of maximum total weight.

For every integer \(k \ge 2\), the \(k\)-cube \(Q_k\) admits a perfect matching: there is a set of edges of \(Q_k\), no two sharing a vertex, that together cover every vertex.

For every natural number \(n\), the number of perfect matchings of the complete graph \(K_{2n}\) on \(2n\) vertices — that is, the number of ways to partition its vertex set into \(n\) disjoint pairs, each joined by an edge — is

For every natural number \(n\), the complete bipartite graph \(K_{n,n}\), whose two vertex classes each have \(n\) vertices and whose edges are exactly the pairs joining a vertex of one class to a vertex of the other, has exactly \(n!\) perfect matchings.

Let \(G\) be a tree on a finite vertex set — a connected, acyclic simple graph. Then any two perfect matchings of \(G\) coincide; that is, \(G\) has at most one perfect matching.

For every natural number \(n\), the complete bipartite graph \(K_{n,n}\), whose two vertex classes each have \(n\) vertices and whose edges join every vertex of one class to every vertex of the other, is \(1\)-factorable: its edge set decomposes into edge-disjoint \(1\)-factors (perfect matchings).

For every natural number \(n\), the complete graph \(K_{2n}\) on \(2n\) vertices is \(1\)-factorable; that is, its edge set can be partitioned into edge-disjoint \(1\)-factors.

Let \(G\) be a finite simple graph on \(n\) vertices, and suppose that \(n\) is even and that the minimum degree \(\delta \) of \(G\) satisfies \(n + 2 \le 2\delta \), that is, \(\delta \ge \tfrac {n}{2} + 1\). Then \(G\) has a \(3\)-factor: a spanning subgraph in which every vertex has degree exactly \(3\).

For every integer \(n \ge 1\), the complete graph \(K_{2n+1}\) on \(2n+1\) vertices can be expressed as the edge-disjoint union of \(n\) connected \(2\)-factors. Concretely, there exist spanning subgraphs \(H_1, \ldots , H_n\) of \(K_{2n+1}\), each of which is \(2\)-regular (every vertex has exactly two neighbours in it) and connected, whose edge sets are pairwise disjoint and whose union is all of \(K_{2n+1}\).

Let \(G\) be a simple graph on a finite vertex set \(V\) that is bipartite with parts \(X\) and \(Y\): the sets \(X\) and \(Y\) are disjoint, together they exhaust \(V\) (so \(X \cup Y = V\)), and every edge of \(G\) joins a vertex of \(X\) to a vertex of \(Y\). For a set \(S \subseteq V\) write \(N(S) = \bigcup _{v \in S} N(v)\) for the set of all vertices adjacent to some vertex of \(S\). Then \(G\) has a perfect matching if and only if \(\left\lvert S\right\rvert \le \left\lvert N(S)\right\rvert \) for every set \(S \subseteq V\).

Let \(G\) be a bipartite graph with vertex classes \(X\) and \(Y\), and let \(k\) be a positive integer. If \(G\) is \(k\)-regular, then \(G\) is \(1\)-factorable; that is, \(G\) decomposes into edge-disjoint \(1\)-factors.

Let \(G\) be a finite simple graph, and suppose \(G\) is regular of degree \(2k\) for some natural number \(k\), meaning every vertex has exactly \(2k\) neighbours. Then \(G\) is \(2\)-factorable: its edges decompose into finitely many pairwise edge-disjoint \(2\)-factors, that is, edge-disjoint \(2\)-regular spanning subgraphs whose union is all of \(G\).

Let \(A\) be an \(m \times n\) matrix with entries in \(\{ 0,1\} \), and call a *line* of \(A\) any single row or single column. Consider two quantities: the minimum number \(c\) of lines needed to cover all the \(1\)-entries of \(A\) (that is, the least value of \(\left\lvert R\right\rvert + \left\lvert C\right\rvert \) over all sets \(R\) of rows and \(C\) of columns such that every entry equal to \(1\) lies in a row of \(R\) or a column of \(C\)), and the maximum number \(d\) of \(1\)-entries of \(A\) no two of which share a line (that is, the largest size of a set of positions with entry \(1\) whose members have pairwise distinct rows and pairwise distinct columns). Then \(c = d\).

Let \(G\) be a finite bipartite graph with bipartition \((X, Y)\), and for a set \(S \subseteq X\) write \(N(S) = \bigcup _{v \in S} N(v)\) for the set of vertices adjacent to some vertex of \(S\). If \(M\) is a maximum matching of \(G\), then

where \(\lvert M\rvert \) denotes the number of edges of \(M\).

Let \(G\) be a finite bipartite graph with vertex parts \(X\) and \(Y\), so that every edge of \(G\) joins a vertex of \(X\) to a vertex of \(Y\), and suppose \(\left\lvert X\right\rvert = \left\lvert Y\right\rvert = n\). Write \(\varepsilon \) for the number of edges of \(G\), and let \(k\) be a natural number. If \((k-1)\, n \lt \varepsilon \), then \(G\) contains a matching consisting of exactly \(k\) edges.

Let \(m\) and \(n\) be finite index sets, and let \(Q = (Q_{ij})_{i \in m,\, j \in n}\) be a real matrix whose every row sums to \(1\), so that \(\sum _{j \in n} Q_{ij} = 1\) for each \(i \in m\), and whose every column sums to \(1\), so that \(\sum _{i \in m} Q_{ij} = 1\) for each \(j \in n\). Then the two index sets have the same size, \(\left\lvert m\right\rvert = \left\lvert n\right\rvert \); that is, \(Q\) is square.

Let \(H\) be a finite group and let \(K \le H\) be a subgroup. Then there exist a natural number \(n\) and elements \(h_1, \dots , h_n \in H\) such that the assignment \(i \mapsto h_i K\), sending each index to the corresponding left coset viewed as a subset of \(H\), is a bijection from \(\{ 1, \dots , n\} \) onto the collection of all subsets of \(H\), and, simultaneously, the assignment \(i \mapsto K h_i\), sending each index to the corresponding right coset, is also a bijection from \(\{ 1, \dots , n\} \) onto the collection of all subsets of \(H\).

Let \(G\) be a finite simple graph that is \(k\)-regular for some integer \(k \ge 1\), and whose edge connectivity satisfies \(\kappa '(G) \ge k - 1\). If \(G\) has an even number of vertices, then \(G\) has a perfect matching, that is, a set of pairwise disjoint edges that together cover every vertex.

Let \(G\) be a finite tree, and for a graph \(H\) write \(o(H)\) for the number of connected components of \(H\) having an odd number of vertices. Then \(G\) has a perfect matching if and only if \(o(G - v) = 1\) for every vertex \(v\) of \(G\), where \(G - v\) denotes the graph obtained from \(G\) by deleting \(v\) together with all edges incident to it.

Let \(G\) be a finite simple graph on vertex set \(V\), and let \(M\) be a maximum matching of \(G\), so that no matching of \(G\) has more edges than \(M\). For a set \(S \subseteq V\), write \(o(G - S)\) for the number of connected components having an odd number of vertices in the subgraph of \(G\) induced on \(V \setminus S\). Then

where \(\left\lvert M\right\rvert \) is the number of edges of \(M\) and the maximum ranges over all subsets \(S\) of \(V\).

Let \(G\) be a finite simple graph on \(n\) vertices with \(m\) edges and minimum degree \(\delta \). Suppose that \(n\) is even, that \(2\delta \lt n\), and that

Then \(G\) has a perfect matching.