Zes vrouwen vallen elk op een aantal vrijgezelle mannen. Kunnen de zes vrouwen met de zes mannen worden gekoppeld, zó dat elke vrouw een man van haar keuze trouwt?

In sommige gevallen is het eenvoudig om te zien dat er geen oplossing mogelijk is. Als er een dame bij is die niemand leuk vindt, lukt het niet. Ook als er twee vrouwen zijn die enkel één en dezelfde man willen, loopt het mis.

Kan het met de volgende keuze?
Een nodige en voldoende voorwaarde op het bestaan van een oplossing is dat iedere k dames samen met tenminste k  verschillende mannen willen trouwen. Hierbij is . Omdat de dames a,c,d en f samen maar drie verschillende mannen willen huwen, namelijk de nummers 2,3 en 6, is het dus onmogelijk alle zes dames uit te huwelijken!

Deze stelling, die dateert uit 1933, werd bewezen door de Engelse wiskundige Philip Hall ( 1904-1982).

Als het zo is dat we niet alle dames kunnen koppelen, dan kunnen we ons wel de vraag stellen: wat is het maximaal aantal dames dat kan gekoppeld worden?

Hiervoor vertalen we het probleem naar een probleem met grafen: Voor iedere vrouw is er een bijhorend punt in A en voor iedere man is er een punt in B. We trekken een lijn tussen een vrouw en een man, als zij met hem wilt trouwen.

De resulterende graaf heet bipartiet omdat de punten zijn opgedeeld in twee groepjes en lijnen altijd punten uit verschillende groepen verbinden. Een aantal lijnen noemt men een matching als geen twee lijnen eenzelfde eindpunt hebben. Een uithuwelijking is dus eigenlijk een matching. In het rood staat hierboven een matching met 4 lijnen. Een betere matching wordt gegeven door volgende figuur, waarin 5 vrouwen kunnen worden uitgehuwelijkt.