Teorema (Hall, 1935)

Teorema 2.2 (Hall, 1935) Misal G adalah graf bipartit dengan partisi (X,Y). Maka G mengandung sebuah matching saturates setiap simpul di X jika dan hanya jika │N(S)│≥ │S│ untuk setiap S ⊆ X. (2.2)

Bukti : Asumsikan G mengandung matching M yang saturates tiap simpul di X, misalkan S adalah subset X. Karena tiap simpul di S matched ke simpul di N(S) dalam M, kita jelas mempunyai │N(S)│≥ │S│.

Kebalikannya, asumsikan bahwa G adalah sebuah graf bipartit memenuhi teorema (2.2), dan misalkan G tidak mempunyai matching yang saturates tiap simpul di X. Ambil kontradiksi, misalkan M* menjadi matching maksimum dari G. M* tidak semua matching saturated di X. Misal u sebuah M*–Unsaturated simpul di X. Misal Z adalah himpunan semua simpul yang terhubung dengan u dengan lintasan M*–alternating. Karena M* adalah sebuah matching maksimum, oleh teorema (2.1) Bahwa u adalah satu – satunya simpul M*–Unsaturated dalam Z. Misal S = Z ∩ X dan T = Z ∩ Y (lihat gambar 2.11)

Jelas, S\{u} matching pada M* dengan simpul di T. Oleh karena itu

│T│ = │S│- 1 (2.3)

Dan N(S) T. Jadi

N(S) = T (2.4)

Karena setiap simpul di N(S) terhubung pada u oleh lintasan M*–alternating.

(2.3) dan (2.4) Mengimplikasikan bahwa

│N(S)│=│S│ – 1 < │S│

Terjadi kontadiksi asumsi (2.2)

Pembuktian diatas menyediakan sebuah dasar algoritma yang baik untuk menemukan sebuah matching maksimum dalam sebuah graf bipartit, algoritma tersebut algoritma Hungarian.