Hall's Marriage Theorem - Graph Theoretic Formulation

Graph Theoretic Formulation

When S is finite, the marriage theorem can be expressed using the terminology of graph theory. Let S = (A₁, A₂, ..., A_n) where the A_i are finite sets which need not be distinct. Let the set X = {A₁, A₂, ..., A_n} (that is, the set of names of the elements of S) and the set Y be the union of all the elements in all the A_i. We form a finite bipartite graph G:= (X + Y, E), with bipartite sets X and Y by joining any element in Y to each A_i which it is a member of. A transversal (SDR) of S is an X-saturating matching (a matching which covers every vertex in X) of the bipartite graph G.

For a set W of vertices of G, let denote the neighborhood of W in G, i.e. the set of all vertices adjacent to some element of W. The marriage theorem (Hall's Theorem) in this formulation states that an X-saturating matching exists if and only if for every subset W of X

In other words every subset W of X has enough adjacent vertices in Y.

Given a finite bipartite graph G:= (X + Y, E), with bipartite sets X and Y of equal size, the marriage theorem provides necessary and sufficient conditions for the existence of a perfect matching in the graph.

A generalization to arbitrary graphs is provided by the Tutte theorem.