Hall's Marriage Theorem gives necessary and sufficient conditions for a maximal matching to exist between the two sets of a bipartite graph. It has a wide variety of real-world applications, particularly in optimization problems.
Statement of result
Let G be a bipartite graph with bipartition X and Y. Then there is a maximal matching from X to Y if and only if Hall's condition is satisfied: |Γ(A)|>=|A| for all subsets A of X. Here Γ(A) denotes the set of neighbours of the vertices in A.
For a full mathematical treatment of this result, see the proof of Hall's Marriage Theorem.
Explanation
We think of a bipartite graph as two sets of points, X and Y, with lines going from elements in X to elements in Y. Because the graph is bipartite there are no lines going from elements in X to other elements in X, and no lines going from elements in Y to other elements in Y. Consider the following simple example, where X={1,2,3} and Y={4,5,6,7}.
1--4
/
/
2--5
3--6
\
\
7
A matching is a set of edges which link every element in X to a different one in Y. Hence for this graph, {14,25,36} is a matching. Another matching would be {14,25,37}. Hall's theorem gives us conditions for such a matching to exist. We have
Γ({1}) = {4}, Γ({2}) = {4,5}, Γ({3}) = {6,7},
Γ({1,2}) = {4,5}, Γ({1,3}) = {4,6,7}, Γ({2,3}) = {4,5,6,7},
Γ({1,2,3}) = {4,5,6,7}.
The number of neighbours of any subset A of X is greater than or equal to the size of A, hence Hall's condition is satisfied, and we deduce that a matching exists, as expected.
Conversely, suppose we remove the edge going from 2 to 5. Now no matching exists, since 1 and 2 must both be linked to 4. We expect Hall's condition to fail, and indeed it does, since
Γ({1,2}) = {4},
|Γ({1,2})| < |{1,2}|.
This is the strength of Hall's theorem. In many situations in mathematics, we have either necessary conditions for something to be true, or sufficient conditions for something to be true, but not both.
Hall's condition on the other hand provides a concrete test of whether or not a matching exists.
An example of real world application would be a supermarket chain wanting to find a way of transporting goods from its depots to all its stores. We think of the elements in X as the depots and the elements in Y as the stores, and draw a line from a depot to a store if they are geographically close. Then a matching from X to Y would correspond to an efficient transport scheme between all the sites.
The theorem is known as Hall's Marriage Theorem because originally elements in X were thought of a women and elements in Y were thought of as men. A matching between the two sets corresponded to marrying each woman to a man.
Extensions
In a real-world situation we may not always be interested in a perfect matching. Often the following result is useful:
"Let G be a bipartite graph with bipartition X and Y. Then there exists a matching of |X|-d vertices if and only if |Γ(A)|>=|A|-d, for all subsets A of X."
This can be proved by introducing d extra elements in Y which are connected to every element in X. Hall's condition then holds in this new graph, and we may find a matching. Removing the extra elements gives the required partial matching in the original graph.
Similarly, we may wish to match more than each element in X to a fixed number d of elements in Y. This is possible if and only if |Γ(A)|>=d|A| for all subsets A of X. This can be proved by introducing d clones of every element in X, which are connected to the same elements in Y. We find a matching in this new graph, and then identify each of the clones with the corresponding original element, which gives the required matching in the original graph.