Matching Theory

Theorem . Let G = (V, E) be bipartite with V partitioned as X ∪ Y. A complete matching of X into Y exists if and only if for every subset of X, | A | ≤ | R(A) |, where R(A) is the subset of Y consisting of those vertices each of which is adjacent to at least one vertex in A.
Proof. With V partitioned as X ∪ Y, let X = {x1, x2, ......, xm} and Y = {y1, y2, ......, yn} Construct a transport network N that extends graph G by introducing two new vertices a and z (the source and sink).
For each vertex xi, 1 ≤ i ≤ m, draw edge (a, xi) ; for each vertex yj, 1 ≤ j ≤ n, draw edge (yj, z).
Each new edge is given a capacity of 1. Let M be any positive integer that exceeds | X |. Assign each edge in G the capacity M.
The original graph G and its associated network N appear as shown in Fig. (4.88). It follows that a complete matching exists in G if and only if there is a maximum flow in N that uses all edges (a, xi), 1 ≤ i ≤ m.
Then the value of such a maximum flow is m = | X |.

We shall prove that there is a complete matching in G by showing that C(P, P ) ≥ | X | for each cut (P, P ) in N. So if (P, P ) is an arbitrary cut in the transport network N, let us define A = X ∩ P and B = Y ∩ P. Then A ⊆ X where we shall write A = {x1, x2, ......, xi} for some 0 ≤ i ≤ m. Now P consists of the source a together with the vertices in A and the set B ⊆ Y, as shown in Fig. (4.89)(a). In addition, P = (X – A) ∪ (Y – B) ∪ {z}.
Since each of these edges has capacity 1, C(P, P ) = | X – A | | B | = | X | – | A | | B |, with B ⊇ R(A), we have | B | ≥ R(A), and since | R(A) | ≥ | A |, it follows that | B | ≥ | A |. Consequently, c(P, P ) = | X | (| B | – | A |) ≥ | X |.
Therefore, since every cut in network N has capacity at least | X |, such a flow will result in exactly | X | edges from X to Y having flow 1, and this flow provides a complete matching of X into Y. Conversely, suppose that there exists a subset A of X where | A | > | R(A) |.
Let (P, P ) be the cut shown for the network in Fig. (4.89)(b), with P = {a} ∪ A ∪ R(A) and P = (X – A) ∪ (Y – R(A)) ∪ {z}. Then C(P, P ) is determined by (i) the edges from the source a to the vertices in X – A and (ii) the edges from the vertices in R(A) to the sink z. Hence C(P, P ) = | X – A | | R(A) | = | X | – (| A | – | R(A) |) < | X |, since | A | > | R(A) |. The network has a cut of capacity less than | X |, it follows that any maximum flow in the network has value smaller than | X |.
Therefore, there is no complete matching from X into Y for the given bipartite graph G.