Wyobraźmy sobie, że mamy grupę \(k\) kobiet i \(m\) mężczyzn, wszyscy stanu wolnego, oraz każda kobieta ma listę mężczyzn, których byłaby skłonna poślubić.
Czy jest możliwe takie połączenie osób w pary (przez parę rozumiemy skojarzenie kobieta-mężczyzna) by każda panna dostała swojego kawalera?
Okazuje się, że tak - o ile spełniony jest warunek, że każde \(k\) dziewczyn zna co najmniej \(k\) kawalerów.
W takiej sytuacji odpowiednie połączenie kobiet i mężczyzn nazywamy skojarzeniem doskonałym, a powyższe twierdzenie podające warunek konieczny i wystarczający zarazem, nazywamy twierdzeniem Halla (o kojarzeniu małżeństw).
Przykład:
Połączenia pokazują którego z kawalerów zna dana panna.
W tej grupie istnieje skojarzenie doskonałe.
A jak sytuacja wygląda w przypadku poniższej grupy z tak zadaną siatką znajomości?
Warunek konieczny nie jest spełniony, zatem dla tej grupy nie istnieje skojarzenie doskonałe (ponieważ da się wskazać dwie panny, które znają tylko jednego mężczyznę).
Twierdzenie Halla znajduje zastosowanie w wielu sytuacjach ze świata rzeczywistego i być może małżeństwa nie są tutaj najlepszym przykładem. Inne przypadki sytuacji, które dają się modelować w podobny sposób to np. aplikowanie studentów na uczelnie wyższe lub przydzielanie zadań pracownikom w firmie.