In een bepaald stadje zijn n  ongetrouwde jongens en  n  ongetrouwde meisjes. Stel dat elke jongen met  k van de meisjes zou kunnen trouwen ( = die meisjes willen wel en hijzelf wil ook wel) en dat elk meisje met k jongens zou kunnen trouwen (= zij wil en hij wil). Laat zien dat het dan mogelijk is dat iedereen gaat trouwen.

Om dit te laten zien maken we gebruik van de stelling van Hall, ook wel de huwelijksstelling genoemd. Nog een keer herhaald:

Stel je hebt een collectie An van n verzamelingen:  An = {V1,V2,V3,...,Vn} Is het dan mogelijk om uit elke verzameling een verschillend element te kiezen (een vertegenwoordiger)? Zo'n verzameling van vertegenwoordigers heet een SDR = System of Distinct Representatives De stelling van Hall luidt: Er is een SDR te maken van An  Elke collectie van k deelverzamelingen uit An bevat minstens k elementen

Een bewijs daarvan vind je HIER

Hoe kunnen we deze stelling gebruiken bij ons huwelijksprobleem?

(rest volgt later)