Teorema (Hall, 1935) Jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai matching sempurna.
Bukti. Misal G adalah k–regular bipartit dengan partisi (X,Y). Karena G k–regular, k│X│=│E│= k│Y│, karena k > 0, sehingga│X│=│Y│. Misal S himpunan bagian dari X dan misalkan E1 dan E2 himpunan sisi incident dengan simpul di S dan N(S). Oleh definisi N(S), E1 ⊆ E2 dan oleh karena itu
k│N(S)│=│ E2│≥│ E1│= k │S│
Mengikuti │N(S)│ ≥│S│ karena teorema 2.2 G mempunyai matching M–saturating setiap simpul di X. maka│X│=│Y│, M adalah matching sempurna.
Tidak ada komentar:
Posting Komentar