Dado $G = (V,E)$ um grafo, para cada $v\in V$ denote por $E(v)$ o subconjunto de arestas de $V$ das quais $v$ é uma das pontas. Fixe ainda $\leq_v$ uma ordem total sobre $E(v)$, isto é, uma relação sobre esse conjunto que satisfaz as seguintes propriedades:
Dizemos que $\leq_v$ é uma ordem de preferência do vértice $v$ entre seus vizinhos. Com isso, mediante uma família de ordens de preferências $\{\leq_v : v \in V\}$, dizemos que um emparelhamento $M$ é estável se, dada uma aresta não emparelhada $e\in E\setminus M$, existe uma aresta emparelhada $f\in M$ que possui uma extremidade $v$ em comum com $e$ tal que $e <_v f$.