Editing Hall's marriage theorem (section)

=== Equivalence of the combinatorial formulation and the graph-theoretic formulation ===
A problem in the combinatorial formulation, defined by a finite family of finite sets <math>\mathcal F</math> with union <math>X</math> can be translated into a bipartite graph <math>G=(\mathcal F,X,E)</math> where each edge connects a set in <math>\mathcal F</math> to an element of that set. An <math>\mathcal F</math>-perfect matching in this graph defines a system of unique representatives for <math>\mathcal F</math>.  In the other direction, from any bipartite graph <math>G=(X,Y,E)</math> one can define a finite family of sets, the family of neighborhoods of the vertices in <math>X</math>, such that any system of unique representatives for this family corresponds to an <math>X</math>-perfect matching in <math>G</math>. 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 <math>G=(X,Y,E)</math>, every vertex in <math>X</math> should have finite [[degree (graph theory)|degree]]. The degrees of the vertices in <math>Y</math> are not constrained.