Editing Hall's marriage theorem (section)

== Graph theoretic formulation ==
[[File:Halls theorem matching graph theory2.svg|thumb|blue edges represent a matching]]
Let <math>G=(X,Y,E)</math> be a finite [[bipartite graph]] with bipartite sets <math>X</math> and <math>Y</math> and edge set <math>E</math>.  An ''<math>X</math>-perfect matching'' (also called an ''<math>X</math>-saturating matching'') is a [[Matching (graph theory)|matching]], a set of disjoint edges, which covers every vertex in <math>X</math>.

For a subset <math>W</math> of <math>X</math>, let <math>N_G(W)</math> denote the [[Neighbourhood (graph theory)|neighborhood]] of <math>W</math> in <math>G</math>, the set of all vertices in <math>Y</math> that are [[Adjacent (graph theory)|adjacent]] to at least one element of <math>W</math>.  The marriage theorem in this formulation states that there is an <math>X</math>-perfect matching [[if and only if]] for every subset <math>W</math> of <math>X</math>: <math display=block>|W| \leq |N_G(W)|.</math> In other words, every subset <math>W</math> of <math>X</math> must have sufficiently many neighbors in <math>Y</math>.

=== Proof ===
====Necessity====
In an <math>X</math>-perfect matching <math>M</math>, every edge incident to <math>W</math> connects to a distinct neighbor of <math>W</math> in <math>Y</math>, so the number of these matched neighbors is at least <math>|W|</math>. The number of all neighbors of <math>W</math> is at least as large.

====Sufficiency====
Consider the [[contrapositive]]: if there is no <math>X</math>-perfect matching then Hall's condition must be violated for at least one <math>W\subseteq X</math>.  Let <math>M</math> be a maximum matching, and let <math>u</math> be any unmatched vertex in <math>X</math>. Consider all ''alternating paths'' (paths in <math>G</math> that alternately use edges outside and inside <math>M</math>) starting from <math>u</math>. Let <math>W</math> be the set of vertices in these paths that belong to <math>X</math> (including <math>u</math> itself) and let <math>Z</math> be the set of vertices in these paths that belong to <math>Y</math>. Then every vertex in <math>Z</math> is matched by <math>M</math> to a vertex in <math>W</math>, 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 <math>M</math> or not. Therefore, the size of <math>W</math> is at least the number <math>|Z|</math> of these matched neighbors of <math>Z</math>, plus one for the unmatched vertex <math>u</math>. That is, <math>|W|\ge |Z|+1</math>. However, for every vertex <math>v\in W</math>, every neighbor <math>w</math> of <math>v</math> belongs to <math>Z</math>: an alternating path to <math>w</math> can be found either by removing the matched edge <math>vw</math> from the alternating path to <math>v</math>, or by adding the unmatched edge <math>vw</math> to the alternating path to <math>v</math>. Therefore, <math>Z=N_G(W)</math> and <math>|W|\ge |N_G(W)|+1</math>, 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 <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.