1-factorable

Jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai 1–factorable :

Misal graf G adalah k–regular graf bipartit dengan k > 0. Sesuai teorema 2.2 (Hall, 1935), kondisi matching pada G, karena menurut corollary 2.1 jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai matching sempurna. Warnai semua sisi pada matching sempurna dengan satu warna, kemudian memindahkannya dari G, kita memperoleh (k–1)–regular graf bipartit. Ulangi proses ini k kali dan selesai.