Hall’s marriage theorem, proof of
We prove Hall’s marriage theorem by induction
on |S|, the size of S.
The theorem is trivially true for |S|=0.
Assuming the theorem true for all |S|<n, we prove it for |S|=n.
First suppose that we have the stronger condition
|∪T|≥|T|+1 |
for all ∅≠T⊂S. Pick any x∈Sn as the representative of Sn; we must choose an SDR from
S′={S1∖{x},…,Sn-1∖{x}}. |
But if
{Sj1∖{x},…,Sjk∖{x}}=T′⊆S′ |
then, by our assumption,
|∪T′|≥|∪ki=1Sji|-1≥k. |
By the already-proven case of the theorem for S′ we see that we can indeed pick an SDR for S′.
Otherwise, for some ∅≠T⊂S we have the “exact” size
|∪T|=|T|. |
Inside T itself, for any T′⊆T⊂S we have
|∪T′|≥|T′|, |
so by an already-proven case of the theorem we can pick an SDR for T.
It remains to pick an SDR for S∖T which avoids all elements of ∪T (these elements are in the SDR for T). To use the already-proven case of the theorem (again) and do this, we must show that for any T′⊆S∖T, even after discarding elements of ∪T there remain enough elements in ∪T′: we must prove
|∪T′∖∪T|≥|T′|. |
But
|∪T′∖∪T| | =|⋃(T∪T′)|-|∪T|≥ | (1) | |||
≥|T∪T′|-|T|= | (2) | ||||
=|T|+|T′|-|T|=|T′|, | (3) |
using the disjointness of T and T′. So by an already-proven case of the theorem, S∖T does indeed have an SDR which avoids all elements of ∪T.
This the proof.
Title | Hall’s marriage theorem, proof of |
---|---|
Canonical name | HallsMarriageTheoremProofOf |
Date of creation | 2013-03-22 12:45:12 |
Last modified on | 2013-03-22 12:45:12 |
Owner | mps (409) |
Last modified by | mps (409) |
Numerical id | 10 |
Author | mps (409) |
Entry type | Proof |
Classification | msc 05D15 |