Sumber: huffpost.com

Mumun adalah seorang mak comblang, dia hendak menjodohkan 4 laki-laki kepada 4 perempuan. Dia bertanya kepada para laki-laki, siapa perempuan yang mereka sukai kemudian Mumun membuat diagram sebagai berikut.

Diagram 1

Tanda garis adalah kesukaan. Adi dan Galuh sama-sama suka Citra. Bejo menyukai 2 perempuan sekaligus yaitu Ajeng dan Dea, sedangkan Didit naksir Berliana.

Apakah Mumun bisa menjodohkan mereka semua? Apakah terjadi kesesuaian? Yaitu semua laki-laki dan perempuan mendapatkan pasangan tanpa ada satupun yang tertinggal. Mmm… sepertinya tidak mungkin karena Adit dan Galuh menyukai perempuan yang sama. Karena tidak ada kesesuaian, Mumun menyuruh meraka semua kembali berkencan satu-sama lain, Mumun berharap para lelaki mengubah pikirannya. Oh.. stratregi Mumun tepat, dia memperbarui diagramnya sebagai berikut

Diagram 2

Mmm… sepertinya juga belum ada kesesuaian karena pada diagram 2, Didit dan Galuh sama-sama menyukai Ajeng. Kembali Mumun melakukan strategi yang sama dan kembali dia memperbarui diagramnya.

Diagram 3

Nah… sepertinya baru terjadi kesesuaian. Mumun bisa menjodohkan Adi – Citra, Bejo – Berliana, Didit – Ajeng dan Galuh – Dea.

Sekarang timbul pertanyaan

Apa syarat suatu digaram sehingga terjadi kesesuaian?

Peranyaan diatas dijawab oleh teorema berikutnya.

Teorema Pernikahan: Diberikan himpunan laki-laki A dan himpunan perempuan B dengan |A| = |B|, kesesuaian hanya akan terjadi jika hanya jika untuk setiap himpunan bagian X ⊆ A terdapat Y ⊆ A yaitu perempuan-perempuan yang disukai para lelaki di X dengan |X| ≤ |Y|.

Teorema Pernikahan dibuktikan oleh Philip Hall (1935) sehingga sering disebut Teorema Pernikahan Hall atau sederhananya cukup disebut Teorema Hall.

Sekarang mari coba kita lihat diagram 1, pada diagaram 1 terlihat Andi dan Galuh sama-sama menyukai Citra.  Dengan kata lain, kita mendapatkan X = {Andi, Galuh} dan Y= {Citra} dengan |x| > |Y|,  bertentangan dengan Teorema perkawinan. Itulah sebabnya tidak terjadi kesesuaian di diagram 1. Hal serupa juga terjadi pada diagram 2.