"Marriage Theorem" Revisted

The marriage theorem discussed in a preivous post has been established in Graph Theory. The following theorem appeared in the book titled Introduction to Graph Theroem by Gary Chartrand and Ping Zhang.

In a collection of r women and s men, where 1<=r<=s, a total of r marriages between acquainted couples is possible if and only if for each integer k with 1<=k<=r, every subset of k women is collectively acquainted with at least k men.

The theorem deals with the matching problem between two sets in Graph Theory. Anoother form of the theorem is as following,

Let G be a bipartite graph with partite sets U and W such that r=|U|<=
|W|. Then G contains a matching of cardinality r if and only if U is neighborly.

Neighborly is defined as following,

Let G be a bipartite graph with partite sets U and W such that |U|<=|W|. For a nonempty set X of U, the neighborhood N(x) of X is the union of the neighborhoods N(x), where x blelongs to X. Equivalently, N(x) consists of all those vertices of W that are neighbors of one or more vertices in X. The partite set U is said to be neighborly if |N(x)|>=|X| for every nonempty subset X of U.

In plain words, if there is a subset of U which colletively know fewer members of W than the number of themselves, it will be impossible to find a 1-to-1 match for U from W.