|
We prove Hall's marriage theorem by induction on
, the size of .
The theorem is trivially true for .
Assuming the theorem true for all
, we prove it for
.
First suppose that we have the stronger condition
for all
. Pick any as the representative of ; we must choose an SDR from
But if
then, by our assumption,
By the already-proven case of the theorem for we see that we can indeed pick an SDR for .
Otherwise, for some
we have the “exact” size
Inside itself, for any
we have
so by an already-proven case of the theorem we can pick an SDR for .
It remains to pick an SDR for
which avoids all elements of (these elements are in the SDR for ). To use the already-proven case of the theorem (again) and do this, we must show that for any
, even after discarding elements of there remain enough elements in : we must prove
But
using the disjointness of and . So by an already-proven case of the theorem,
does indeed have an SDR which avoids all elements of .
This completes the proof.
|