Definição

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:

• Reflexiva: $e \leq _v e$ para toda aresta $e\in E(v)$;
• Anti-simétrica: Se $e \leq _v f$ e $f \leq_v e$, para certas arestas $e,f \in E(v)$, então $e=f$;
• Transitiva: Dadas $e,f,g \in E(v)$ arestas tais que $e \leq_v f $ e $f \leq_v g$, tem-se que $e \leq_v g$.
• Dois elementos são comparáveis: Dadas duas arestas $e,f \in E(v)$, tem-se que $e \leq_v f$ ou $f \leq_v e$.

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$.