Bewijs van de stelling van Hall

Het bewijs van de stelling van Hall.

De stelling:

Stel je hebt een collectie A_n van n verzamelingen: A_n = {V₁,V₂,V₃,...,V_n}
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 A_n

Elke collectie van k deelverzamelingen uit A_n bevat minstens k elementen

De laatste voorwaarde waaraan A_n moet voldoen heet vanaf nu de huwelijksvoorwaarde.
Het bewijs ervan gaat met inductie als volgt:

Stel dat de stelling geldt voor A_nDus:

A_n voldoet aan de huwelijksvoorwaarde

A_n heeft een SDR ..........(1)

Voeg nu verzameling V_n+1 toe aan de collectie, die wordt dan dus A_n+1 = {V₁,V₂,V₃,...,V_n,V_n+1}
Nu zijn er twee mogelijkheden:

geval 1. Elke collectie B van b verzamelingen uit A_n heeft méér dan b elementen.
Kies dan een element x_n+1 uit V_n+1 en verwijder deze uit alle andere V's
Dat geeft een nieuwe collectie A_n* = {V₁*,V₂*,V₃*,...,V_n*}
Maar ook deze A_n* voldoet aan de huwelijksvoorwaarde, immers elke collectie B van b verzamelingen had méér dan b elementen dus als je er eentje verwijderd heeft elke nog steeds minstens b elementen.
Omdat A_n* aan de huwelijksvoorwaarde voldoet heeft A_n* volgens de inductiestelling (1) een SDR.
Dan heeft An* met V_n+1 eraan toegevoegd ook een SDR (Kies gewoon x_n+1 als vertegenwoordiger van V_n+1)Dan heeft A_n+1 ook een SDR

geval 2. Er is een collectie B van b verzamelingen uit A_n+1 met precies b elementen.
Haal nu eerst alle verzamelingen V die in deze B zitten uit verzameling A. Wat overblijft noemen we C.
Haal vervolgens alle elementen (dat zijn er dus precies b) uit de verzamelingen in C. Wat er dan nog overblijft noemen we de collectie C^*.
Kies een willekeurige collectie D^* (van d verzamelingen) uit C^* , dan geldt:

aantal elementen in D^*	>= (aantal elementen in D + B) - ( b )	immers bij het weghalen van de elementen die in B zitten zijn er b weggehaald uit C, dus hoogstens b uit D.
	= (d + b) - b
	= d

Omdat kennelijk elke D^* van d verzamelingen uit C^* minstens d elementen heeft heeft C^* een SDR (inductie stap (1))

Maar dan heeft C dus ook een SDR, en wel met allemaal elementen die niet in B zitten
B heeft ook een SDR (B voldoet aan de huwelijksvoorwaarde)
Dus heeft C + B ook een SDR (gewoon beide SDR's samennemen)

In beide gevallen heeft A_n+1 een SDR dus de inductiestap is daarmee bewezen.
De stelling geldt duidelijk voor n = 1.

Daarmee is de stelling van Hall bewezen.