Twierdzenie o kojarzeniu małżeństw (twierdzenie Halla) – przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane w 1935 roku. Jest ono często ilustrowane poprzez przedstawienie następującego problemu:
Mamy dwie grupy – dziewcząt i chłopców – oraz pewną sieć znajomości, to znaczy wiemy, których chłopców z tej grupy zna każda z dziewczyn. Kiedy zachodzi sytuacja, w której każdej dziewczynie można przyporządkować jednego kandydata na męża? Tacy kandydaci nie mogą się powtarzać.
Rozwiązanie tak postawionego problemu nosi nazwę twierdzenia o kojarzeniu małżeństw.
Okazuje się, że warunkiem koniecznym i warunkiem wystarczającym na to, by istniało takie skojarzenie par, jest to, by każda podgrupa dziewcząt licząca k osób znała co najmniej k chłopców.
Twierdzenie Twierdzenie można przełożyć na język matematyki na kilka sposobów:
Wersja dla grafów Niech będzie grafem, i niech będą rozłącznymi podzbiorami zbioru wierzchołków, takimi, że jeśli jest dowolną krawędzią grafu i to spełniony jest warunek
czyli graf jest grafem dwudzielnym.