Wówczas w tym grafie istnieje skojarzenie, którego krawędzie są incydentne ze wszystkimi wierzchołkami z wtedy i tylko wtedy, gdy dla każdego podzbioru wierzchołków zachodzi
gdzie:
to zbiór wierzchołków z połączonych krawędzią z którymkolwiek wierzchołkiem z to moc zbioru
Jeżeli to takie skojarzenie jest pełne (doskonałe).
Wersja dla transwersal Twierdzenie Halla dla transwersal mówi, że dla rodziny istnieje transwersala wtedy i tylko wtedy, gdy dla każdej -elementowej podrodziny rodziny mnogościowa suma wszystkich składowych tej podrodziny ma k lub więcej elementów.
dla każdego
Dowód Podany dowód jest sformułowany dla transwersal, dla grafów jest on analogiczny.
Oczywiste jest, iż jest to warunek konieczny, bowiem gdyby nie był on spełniony i suma mnogościowa elementów pewnej rodziny zbiorów miała mniej niż k-elementów, to nie byłoby możliwe wybranie -elementowego podzbioru złożonego z elementów tej sumy.
Wystarczalność warunku można udowodnić, korzystając z indukcji matematycznej.