Misalkan Anda memiliki graf bipartit \(G\text{.}\) Graf ini terdiri atas dua himpunan simpul \(A\) dan \(B\text{,}\) dengan sejumlah sisi yang menghubungkan beberapa simpul dalam \(A\) dengan beberapa simpul dalam \(B\) (dan, tentu saja, tidak ada sisi di antara dua simpul yang keduanya berada dalam \(A\) atau keduanya berada dalam \(B\)). Pencocokan dari \(A\) adalah subhimpunan sisi sedemikian sehingga setiap simpul \(A\) bersisian dengan tepat satu sisi dalam subhimpunan itu, dan tidak ada simpul dalam \(B\) yang bersisian dengan lebih dari satu sisi dalam subhimpunan tersebut. Dalam penerapannya, kita akan mengasumsikan bahwa \(|A| = |B|\) (kedua himpunan memiliki jumlah simpul yang sama), sehingga setiap simpul pada graf bersisian dengan tepat satu sisi dalam pencocokan.

¹¹

Apa yang kita sebut pencocokan kadang-kadang disebut pencocokan sempurna atau pencocokan lengkap. Istilah tersebut digunakan karena pencocokan yang tidak sempurna juga menarik untuk dipelajari. Kita akan menyebutnya pencocokan parsial.