$G=(V,A)$, avec :

$V = \{s, p\} \cup H \cup F$, où $H$ est l'ensemble des hommes & $F$ celui des femmes.

$A$ = $\{(s,h) : h\in H \} \cup \{(f, p) : f \in F\} \cup \{(h,f) : \{h,f\}$ est un couple compatible$\}$

Tous les arcs sont de capacité 1.