In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations. In each case, the theorem gives a
necessary and sufficient
In logic and mathematics, necessity and sufficiency are terms used to describe a material conditional, conditional or implicational relationship between two Statement (logic), statements. For example, in the Conditional sentence, conditional stat ...
condition for an object to exist:
* The
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
formulation answers whether a
finite
Finite may refer to:
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked for person and/or tense or aspect
* "Finite", a song by Sara Gr ...
collection of
sets has a
transversal—that is, whether an element can be chosen from each set without repetition. Hall's condition is that for any group of sets from the collection, the total unique elements they contain is at least as large as the number of sets in the group.
* The
graph theoretic formulation answers whether a finite
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
has a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
—that is, a way to match each vertex from one group uniquely to an adjacent vertex from the other group. Hall's condition is that any subset of vertices from one group has a
neighbourhood
A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neighbourh ...
of equal or greater size.
Combinatorial formulation
Statement
Let
be a finite
family
Family (from ) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). It forms the basis for social order. Ideally, families offer predictabili ...
of sets (note that although
is not itself allowed to be infinite, the sets in it may be so, and
may contain the same set
multiple times). Let
be the union of all the sets in
, the set of elements that belong to at least one of its sets. A
transversal for
is a subset of
that can be obtained by choosing a distinct element from each set in
. This concept can be formalized by defining a transversal to be the
image
An image or picture is a visual representation. An image can be Two-dimensional space, two-dimensional, such as a drawing, painting, or photograph, or Three-dimensional space, three-dimensional, such as a carving or sculpture. Images may be di ...
of an
injective function
In mathematics, an injective function (also known as injection, or one-to-one function ) is a function that maps distinct elements of its domain to distinct elements of its codomain; that is, implies (equivalently by contraposition, impl ...
such that
for each
. An alternative term for ''transversal'' is ''system of distinct representatives''.
The collection
satisfies the marriage condition when each subfamily of
contains at least as many distinct members as its number of sets. That is, for all
,
If a transversal exists then the marriage condition must be true: the function
used to define the transversal maps
to a subset of its union, of size equal to
, so the whole union must be at least as large. Hall's theorem states that the converse is also true:
The name "marriage theorem" came from
Suppose that each of a (possibly infinite) set of boys is acquainted with a finite set of girls. Under what conditions is it possible for each boy to marry one of his acquaintances? It is clearly necessary that every finite set of ''k'' boys be, collectively, acquainted with at least ''k'' girls... this condition is also sufficient.
Examples

;Example 1
: Consider the family
with
and
The transversal
could be generated by the function that maps
to
,
to
, and
to
, or alternatively by the function that maps
to
,
to
, and
to
. There are other transversals, such as
and
. Because this family has at least one transversal, the marriage condition is met. Every subfamily of
has equal size to the set of representatives it is mapped to, which is less than or equal to the size of the union of the subfamily.

;Example 2
: Consider
with
No valid transversal exists; the marriage condition is violated as is shown by the subfamily
. Here the number of sets in the subfamily is
, while the union of the three sets
contains only two elements.
A lower bound on the different number of transversals that a given finite family
of size
may have is obtained as follows: If each of the sets in
has cardinality
, then the number of different transversals for
is either
if
, or
if
.
Recall that a transversal for a family
is an ordered sequence, so two different transversals could have exactly the same elements. For instance, the collection
,
has
and
as distinct transversals.
Graph theoretic formulation

Let
be a finite
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
with bipartite sets
and
and edge set
. An ''
-perfect matching'' (also called an ''
-saturating matching'') is a
matching, a set of disjoint edges, which covers every vertex in
.
For a subset
of
, let
denote the
neighborhood
A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
of
in
, the set of all vertices in
that are
adjacent to at least one element of
. The marriage theorem in this formulation states that there is an
-perfect matching
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
for every subset
of
:
In other words, every subset
of
must have sufficiently many neighbors in
.
Proof
Necessity
In an
-perfect matching
, every edge incident to
connects to a distinct neighbor of
in
, so the number of these matched neighbors is at least
. The number of all neighbors of
is at least as large.
Sufficiency
Consider the
contrapositive
In logic and mathematics, contraposition, or ''transposition'', refers to the inference of going from a Conditional sentence, conditional statement into its logically equivalent contrapositive, and an associated proof method known as . The contrap ...
: if there is no
-perfect matching then Hall's condition must be violated for at least one
. Let
be a maximum matching, and let
be any unmatched vertex in
. Consider all ''alternating paths'' (paths in
that alternately use edges outside and inside
) starting from
. Let
be the set of vertices in these paths that belong to
(including
itself) and let
be the set of vertices in these paths that belong to
. Then every vertex in
is matched by
to a vertex in
, because an alternating path to an unmatched vertex could be used to increase the size of the matching by toggling whether each of its edges belongs to
or not. Therefore, the size of
is at least the number
of these matched neighbors of
, plus one for the unmatched vertex
. That is,
. However, for every vertex
, every neighbor
of
belongs to
: an alternating path to
can be found either by removing the matched edge
from the alternating path to
, or by adding the unmatched edge
to the alternating path to
. Therefore,
and
, showing that Hall's condition is violated.
Equivalence of the combinatorial formulation and the graph-theoretic formulation
A problem in the combinatorial formulation, defined by a finite family of finite sets
with union
can be translated into a bipartite graph
where each edge connects a set in
to an element of that set. An
-perfect matching in this graph defines a system of unique representatives for
. In the other direction, from any bipartite graph
one can define a finite family of sets, the family of neighborhoods of the vertices in
, such that any system of unique representatives for this family corresponds to an
-perfect matching in
. In this way, the combinatorial formulation for finite families of finite sets and the graph-theoretic formulation for finite graphs are equivalent.
The same equivalence extends to infinite families of finite sets and to certain infinite graphs. In this case, the condition that each set be finite corresponds to a condition that in the bipartite graph
, every vertex in
should have finite
degree. The degrees of the vertices in
are not constrained.
Topological proof
Hall's theorem can be proved (non-constructively) based on
Sperner's lemma
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an ...
.
Applications
The theorem has many applications. For example, for a
standard deck of cards, dealt into 13 piles of 4 cards each, the marriage theorem implies that it is possible to select one card from each pile so that the selected cards contain exactly one card of each rank (Ace, 2, 3, ..., Queen, King). This can be done by constructing a bipartite graph with one partition containing the 13 piles and the other partition containing the 13 ranks. The remaining proof follows from the marriage condition. More generally, any
regular
Regular may refer to:
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instruments, tunings with equal intervals between the paired notes of successive open strings
Other uses
* Regular character, ...
bipartite graph has a perfect matching.
More abstractly, let
be a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
, and
be a finite
index
Index (: indexes or indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on the Halo Array in the ...
subgroup
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
Formally, given a group (mathematics), group under a binary operation  ...
of
. Then the marriage theorem can be used to show that there is a set
such that
is a transversal for both the set of left
coset
In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...
s and right cosets of
in
.
The marriage theorem is used in the usual proofs of the fact that an
Latin rectangle
In combinatorial mathematics, a Latin rectangle is an matrix (where ), using symbols, usually the numbers or as its entries, with no number occurring more than once in any row or column.
An Latin rectangle is called a Latin square. Latin rec ...
can always be extended to an
Latin rectangle when