Editing Hall's marriage theorem (section)

=== 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.