charakterisiert diejenigen bipartiten Graphen, die eine vollständige Korrespondenz besitzen. Dabei heißt eine Korrespondenz M in einem bipartiten Graphen G mit den Partitionsmengen X und Y vollständig, wenn \begin{eqnarray}\vert M\vert=\min\{\vert X\vert,\vert Y\vert\}\end{eqnarray} gilt. Der Satz von Hall aus dem Jahre 1935 ist für die gesamte Graphentheorie von fundamentaler Bedeutung.

Es sei G ein bipartiter Graph mit den Partitions-mengen X und Y so, daß |X| ≤ |Y| gilt.

Der Graph G besitzt genau dann eine vollständige Korrespondenz, wenn für alle S ⊆ X die Bedingung \begin{eqnarray}\vert S\vert\leq \vert N_{G}(S)\vert\end{eqnarray}erfüllt ist, wobei N_G(S) diejenigen Ecken aus Y bedeuten, die zu einer Ecke aus S adjazent sind.

Da dieser Satz implizit in einem Resultat von König (1931) enthalten ist, wird er von manchen Autoren auch „Satz von König-Hall“ genannt.

Wegen der folgenden amüsanten Interpretation ist er außerdem unter dem Namen Heiratssatz bekannt: Ist X eine Menge von Damen, Y eine Menge von Herren und xy ∈ K(G), wenn x ∈ X und y ∈ Y einer Heirat nicht abgeneigt sind, so gibt der Satz eine exakte Bedingung dafür an, wann alle Damen einen geeigneten Heiratspartner finden, ohne Bigamie zu betreiben. Übrigens geht der Spezialfall |X| = |Y| dieses Satzes sogar schon auf Frobenius (1917) zurück.

Eine leichte Folgerung aus dem Heiratssatz ist der sogenannte Haremssatz.

Es sei G ein bipartiter Graph mit den Partitionsmengen X = {x₁, x₂, …, x_n} und Y, und jeder Ecke x_i sei eine natürliche Zahl p_i zugeordnet.

Es gibt genau dann eine Kantenmenge K ⊆ K(G) mit der Eigenschaft, daß jede Ecke x_i mit genau p_i Kanten und jede Ecke y ∈ Y mit höchstens einer Kante von K inzidiert, wenn für alle \begin{eqnarray}S=\{x_{j_{1}},x_{j_{2}},\ldots,x_{j_{t}}\}\subsetq X\end{eqnarray}die Bedingung \begin{eqnarray}\vert N_{G}(S)\vert \geq \sum\limits_{i=1}^{t}p_{j_{i}}\end{eqnarray}erfüllt ist.

Die Interpretation dieses Satzes sei diesmal dem Leser überlassen.

Auch das nächste sehr attraktive Ergebnis von König aus dem Jahre 1916 läßt sich leicht mit Hilfe des Satzes von Hall beweisen.

Die Kantenmenge eines p-regulären bipartiten Graphen läßt sich in p kantendisjunkte perfekte Matchings zerlegen.

Kreise ungerader Länge zeigen, daß dieses Ergebnis für nicht bipartite Graphen seine Gültigkeit verliert.

Alle hier angegebenen Sätze gelten auch für bipartite Multigraphen