1 Emparelhamentos em Grafos

Definição 1.1 Um emparelhamento num grafo G é um conjunto de arestas

não adjacentes entre si, isto é, incidentes em pares de vértices disjuntos dois
a dois.
i) Um vértice incidente numa aresta do emparelhamento diz-se coberto pelo
emparelhamento.
ii) Um emparelhamento M é perfeito se cobre todos os vértices de G.
iii) M é maximal se não existe um emparelhamento M 0 que contenha pro-
priamente M , e é máximo se não existe um emparelhamento com maior
número de arestas.

O problema de determinar um emparelhamento máximo de um grafo pode

ser resolvido pelo estudo de caminhos de um tipo especial: dado um empar-
elhamento qualquer M (não vazio!), um caminho M -alternado é um caminho
em G em que, para quaisquer duas arestas consecutivas, uma pertence a M
e a outra não; se o primeiro e o último vértice de um caminho M -alternado
não são cobertos por M , dizemos que é um caminho M -aumentável.

Teorema 1.2 (Berge): Um emparelhamento M de um grafo G é máximo se

e só se não existe em G um caminho M -aumentável.

Demonstração 1.3 : Se existe um caminho M -aumentável, podemos criar

um emparelhamento maior eliminando as arestas de M que pertencem ao
caminho e incluindo as que não pertencem.
Para provar a recı́proca, suponhamos que M não é máximo e que existe por-
tanto um outro emparelhamento M 0 com mais arestas que M . Considere-se
o grafo H que se obtém de G eliminando as arestas que pertencem a am-
bos os emparelhamentos e as que não pertencem a nenhum deles (ou seja,
conservam-se apenas as arestas da diferença simétrica M 4M 0 ); cada vértice

1
v de H tem grau 0, 1 ou 2 porque v pode ser incidente no máximo a uma
aresta de M e uma de M 0 ; as componentes conexas de H só podem então ser
ou vértices isolados, ou ciclos de ordem par com arestas alternadamente de
M e de M 0 , ou caminhos não fechados também com arestas alternadamente
de M e de M 0 ; como |M 0 | > |M |, o grafo H tem mais arestas de M 0 que
de M e portanto pelo menos uma das componentes de H é um caminho que
começa e termina com arestas de M 0 (que não pertencem a M ); esse caminho
é um caminho M -aumentável no grafo G.

Nota 1.4 O conceito de caminho M -alternado aumentável está na base de

um algoritmo de busca de um emparelhamento máximo num grafo.
Numa descrição informal, o algoritmo tem como dados de entrada um grafo
G, um emparelhamento inicial M em G (que pode ser simplesmente o em-
parelhamento vazio) e um vértice x não coberto por M e produz, através de
uma busca em largura, uma árvore M -alternada com raiz em x.
Se houver um vértice v adjacente a x não coberto por M , poderı́amos substi-
tuir M por M ∪ xv (onde xv designa a aresta unindo esses dois vértices); se
todos os vértices adjacentes a x já estão cobertos por M , o algoritmo cria os
primeiros ramos da árvore, ligando x a todos os vértices adjacentes e cada
um destes ao seu par no emparelhamento M ; em seguida, o algoritmo toma
sucessivamente como vértice activo cada um destes últimos vértices; se em
algum passo, se encontra um vértice adjacente não coberto por M , temos
um caminho M -alternado, com inı́cio em x, e podemos substituir M por um
emparelhamento maior como descrito na demonstração do teorema de Berge;
caso contrário, o algoritmo aumenta a árvore, ligando o vértice activo a cada
um dos vértices adjacentes (ainda não pertencentes àrvore) e estes aos seus
pares em M , e assim por diante.
Este procedimento tem como resultado ou um novo emparelhamento maior
que o inicial ou uma árvore M alternada maximal, ou seja, que não pode ser
aumentada. Nesse caso, infelizmente, não se pode garantir que não existam
caminhos M -alternados aumentáveis. Mas uma análise mais atenta (que se
deixa como desafio) permite mostrar o seguinte: chamemos vértices vermel-

2
hos aos vértices da árvore criada pelo algoritmo que estão (na árvore) a uma
distância par de x (incluindo o próprio x, claro).
Então, se nenhum par de vértices vermelhos for adjacente em G, não existe
um caminho M -alternado aumentável que contenha vértices já incluı́dos na
árvore. Evidentemente, neste caso podemos simplesmente eliminar de G os
vértices da árvore e começar de novo.
Mais geralmente, as mesmas ideias permitem implementar um algoritmo que
produz, em tempo polinomial, um emparelhamento máximo do grafo.

Definição 1.5 Designa-se por α0 (G) o número máximo de arestas de um

emparelhamento.

Recorde-se por outro lado que β(G) é o número mı́nimo de vértices numa
cobertura (uma cobertura é um conjunto de vértices tal que qualquer aresta
do grafo incide em algum dos vértices desse conjunto).
Se M for um emparelhamento, qualquer cobertura tem que conter pelo menos
um dos extremos de cada aresta do emparelhamento; como isto é verdade para
qualquer emparelhamento e qualquer cobertura, temos
α0 (G) ≤ β(G).

Uma outra estimativa mais interessante segue do seguinte raciocı́nio: supon-

hamos que temos em G um emparelhamento qualquer M e seja S um con-
junto de vértices. O subgrafo induzido G[V \ S] pode ter várias componentes
conexas; se uma dessas componentes tiver um número ı́mpar de vértices, pelo
menos um deles não pode estar emparelhado dentro da componente, logo só
poderá estar emparelhado com algum dos vértices de S; e, evidentemente,
cada um destes só pode estar emparelhado com um vértice.
Designando por o(G[V \ S]) o número de componentes conexas com um
número ı́mpar de vértices daquele subgrafo, concluı́mos que o número de
vértices não coberto por M é maior ou igual a
o(G[V \ S]) − |S|.

3
Como isto é verdade para qualquer emparelhamento e qualquer subconjunto
S de vértices, obtém-se assim um majorante para α0 (G).
É de facto possı́vel demonstrar a seguinte
Proposição 1.6 Fórmula de Tutte-Berge: Se G é um grafo com vértices V ,
1
α0 (G) = min{|V | − (o(G[V \ S] − |S|) : S ⊂ V }.
2

1.1 Emparelhamentos em grafos bipartidos

Designamos por G[X, Y ] um grafo bipartido com partição V = X ∪ Y do

conjunto dos vértices.
Recordamos a seguinte caracterização de grafos bipartidos:
Proposição 1.7 Um grafo é bipartido se e só se não tem ciclos de compri-
mento ı́mpar.

Os problemas relacionados com emparelhamentos em grafos bipartidos têm

interesse especial e também resultados especı́ficos que convém mencionar.

Dado um conjunto de vértices S, designa-se por N (S) o conjunto de todos

os vértices adjacentes a algum vértice de S. Evidentemente, para que um
emparelhamento em G[X, Y ] cubra todos os vértices de X, é necessário que
para qualquer S ⊂ X, se tenha |N (S)| ≥ |S|; o teorema seguinte diz-nos que
essa condição é também suficiente:

Teorema 1.8 (Hall): G[X, Y ] tem um emparelhamento que cobre todos os

vértices de X se e só se para todo o S ⊆ X se tem |N (S)| ≥ |S|.

4
Demonstração 1.9 : Como já vimos, a condição é obviamente necessária:
dado S ⊆ X os vértices de S estão emparelhados com o mesmo número de
vértices de Y e portanto |N (S)| ≥ |S|.
Para vermos que a condição é também suficiente, suponhamos que temos um
emparelhamento máximo M que não cobre todos os vértices de X e seja x
um desses vértices não cobertos. Como supômos que M é máximo podemos
assumir que todos os vértices adjacentes a x estão emparelhados. Seja Z o
conjunto dos vértices que podem ser alcançados por um caminho M -alternado
com inı́cio em x; um caminho desse tipo parte de x por uma aresta de A \ M
para um vértice y ∈ Y , passa por uma aresta de M para um vértice de X,
regressa a Y por uma aresta de A \ M e assim por diante.
A hipótese de M ser máximo implica que x é o único vértice de Z não coberto
pelo emparelhamento: se v ∈ Z ∩ X, v está coberto por M pela própria
definição de caminho M -alternado; e se u ∈ Z ∩Y não estivesse emparelhado,
o caminho de x até u seria M -aumentável, contrariando a hipótese de M ser
máximo. Designando S = Z ∩ X e R = Z ∩ Y concluı́mos que os vértices de
S \ x estão emparelhados com os de R e que de facto N (S) = R; mas então
|N (S)| = |S| − 1 e portanto a condição não se verifica.

Corolário 1.10 : Um grafo bipartido G[X, Y ] tem um emparelhamento per-

feito se e só se |X| = |Y | e |N (S)| ≥ |S|, para todo o S ⊆ X.

Tem-se também o seguinte corolário cuja demonstração se deixa como ex-

ercı́cio:

Corolário 1.11 : Se G[X, Y ] é um grafo bipartido regular (ou seja todos os

vértices têm o mesmo grau k > 0), então G[X, Y ] tem um emparelhamento
perfeito.

Tal como acontece com o teorema de Berge, a demonstração do Teorema

de Hall pode ser posta em termos algorı́tmicos: dada uma ordem inicial

5
dos vértices de X, emparelhamos os elementos x1 , x2 , · · · até chegarmos à
situação em que um xk só tem vértices adjacentes já emparelhados; para
descrever mais facilmente o algoritmo, vamos designar os vértices adjacentes
de um determinado vértice como os seus vizinhos, o emparelhamento feito até
aqui como M e quando um vértice está já emparelhado com outro dizemos
que este é o seu par.
Construı́mos (usando um dos algoritmos de busca em grafos) um grafo do
seguinte modo: ligamos x]k a todos os seus vizinhos (que, recorde-se, já estão
emparelhados), ligamos cada um destes ao seu par, ligamos cada um destes a
todos os seus outros vizinhos (se existirem), e assim por diante. A condição
do teorema garante que mais tarde ou mais cedo tem que haver de facto um
elemento de X neste grafo que tem um vizinho, chamemos-lhe v ∈ Y , ainda
não emparelhado: caso contrário, o conjunto S de vértices de X incluı́dos
neste subgrafo teria, digamos m vértices e N (S) teria m − 1 vértices (os
pares dos x ∈ S \ xk ), contradizendo a condição do Teorema. Assim que
encontramos esse v temos na árvore um caminho M -alternado que começa
em xk e termina em v e podemos usá-lo para aumentar o emparelhamento.

Mencionamos a seguir uma das interpretações do teorema de Hall com

importância em combinatória.
Definição 1.12 Dada uma famı́lia S1 , S2 , · · · , Sm de conjuntos, um sistema
de representantes distintos é um conjunto x1 , x2 , · · · , xm tal que
xi ∈ Si ∀i xi 6= xj ∀i 6= j
Podemos associar a uma famı́lia
S desse tipo um grafo bipartido G[X, Y ] em
que X = {1, 2, · · · , m}, Y = Si , e i ∈ X e u ∈ Y são adjacentes se u ∈ Si .
O Teorema de Hall implica então o seguinte
Teorema 1.13 : Uma famı́lia de conjuntos S1 , S2 , · · · , Sm tem um sistema
de representantes distintos se e só se para qualquer subconjunto I ⊆ {1, 2, · · · , m}
se verifica a condição
|∪i∈I Si | ≥ |I|

6
 O Teorema de Hall é equivalente ao seguinte resultado, de que se apresenta
uma demonstração independente:

Teorema 1.14 (König-Egérvary) Num grafo bipartido G[X, Y ], o número

máximo de arestas num emparelhamento é igual ao número mı́nimo de vértices
numa cobertura, ou seja
α0 (G[X, Y ]) = β(G[X, Y ]).

Demonstração 1.15 : Em primeiro lugar, notamos que, para qualquer em-

parelhamento M e qualquer cobertura C num grafo G (não necessariamente
bipartido), se tem
|M | ≤ |C|;
de facto, cada aresta de M incide em (pelo menos) um vértice de C e arestas
a e b de M não podem incidir num mesmo vértice; logo, temos uma aplicação
injectiva de M em C.
Para provar o Teorema basta portanto, dado um emparelhamento M máximo
de G[X, Y ], encontrar uma cobertura C com |M | vértices.

Seja então M um emparelhamento máximo em G[X, Y ] e W ⊂ X o con-

junto de vértices de X em que não incide uma aresta de M . Notamos que
|M | = |X| − |W |.
Sejam S ⊂ X e R ⊂ Y os conjuntos de vértices de cada lado alcançáveis
por um caminho M -alternado com inı́cio em W . Temos, por definição de
caminho M -alternado, que W ⊂ S; além disso, se y ∈ R, então existe uma
aresta de M incidente em y: caso contrário, o caminho M alternado com
inı́cio num vértice w ∈ W e fim em y seria M -aumentável, contrariando o
Teorema de Berge.
Podemos então considerar a aplicação h : R → S \ W que a cada y ∈ R
faz corresponder o único vértice x tal que a aresta xy pertence a M , e verifi-
camos que esta aplicação é uma bijecção: se x ∈ S \ W , a última aresta em
qualquer caminho M alternado com inı́cio em W e fim em x é a aresta de M

7
incidente em x e portanto x é a imagem por h do vértice no outro extremo
dessa aresta. Concluı́mos que
|R| = |S| − |W |.
Definimos então C = (X \S)∪R e verificamos que se trata de uma cobertura:
designamos cada aresta por xy em que x e y são os vértices em que a aresta
incide, respectivamente do lado X e do lado Y ; se x ∈ X \ S, é claro que
a aresta xy está coberta por C; se x ∈ S, então x é o vértice final de um
caminho M -alternado com inı́cio em W ; caso xy ∈ M , a última aresta desse
caminho foi precisamente xy, logo y ∈ R; se xy ∈/ M , o caminho M -alternado
que termina em x pode ser prolongado através de xy até y e portanto, mais
uma vez, y ∈ R e, em qualquer dos dois casos, xy está coberta por C.
Mas
|C| = |X \ S| + |R| = |X| − |S| + |R| = |X| − |W | = |M |
usando as igualdades deduzidas nos parágrafos anteriores.

Nota 1.16 O teorema de König-Egérvary pertence a um tipo de resultados

habitualmente designados por min-max que estabelecem relações de igualdade
entre o máximo de uma certa grandeza e o mı́nimo de outra. Citamos como
exemplo uma das versões do Teorema de Menger: dado um grafo G e x, y ∈
V (G), dois caminhos entre x e y dizem-se disjuntos se não têm outros vértices
em comum; um conjunto de vértices S ⊂ V (G) \ {x, y} separa x e y se estes
dois vértices ficam em componentes conexas diferentes do grafo G \ S (que se
obtém de G eliminando os vértices de S e as arestas neles incidentes).

Teorema 1.17 (Menger) Dado um grafo G e x, y ∈ V (G), o número

máximo de caminhos disjuntos entre x e y é igual ao número mı́nimo de
vértices de um conjunto que separe x e y.

Exercı́cios

8
1. Mostrar que um grafo G é bipartido se e só se para todo o subgrafo
induzido H se verifica a desigualdade
1
α(H) ≥ |VH |.
2
2. Existe algum grafo bipartido com sequência de graus 6, 6, 6, 5, 3, 3, 3, 3, 3?
3. Mostrar que um grafo bipartido regular de grau k > 0 tem um emparel-
hamento perfeito.
4. Determinar quantos emparelhamentos perfeitos tem
a) Kn,n (o grafo bipartido completo em que cada um dos dois conjuntos
estáveis tem n vértices);
b) K2n ;
c) K2n − a em que a é uma aresta de K2n ;
d) K2n − {a, b} em que a e b são arestas de K2n .
5. Se cada peça de um dominó cobre exactamente duas casas de um tab-
uleiro de xadrez, será possı́vel cobrir o tabuleiro com peças do dominó,
deixando apenas duas casas em cantos opostos descobertas?
6. Dizemos que um vértice v de um grafo G é essencial se é coberto por
qualquer emparelhamento máximo de G.
a) Dar um exemplo de um grafo sem vértices essenciais.
b) Mostrar que uma árvore tem sempre vértices essenciais.
7. Suponhamos que um conjunto S tem a decomposição
S = A1 ∪ · · · ∪ An , Ai ∩ Aj = ∅ se i 6= j, |Ai | = m ∀i
e também
S = B1 ∪ · · · ∪ Bn , Bi ∩ Bj = ∅ se i 6= j, |Bi | = m ∀i.
Mostrar que existe uma permutação π dos ı́ndices {1, · · · , n} tal que
Ai ∩ Bπ(i) 6= ∅, ∀i.

9
 Sugestão: Considerar a famı́lia de conjuntos I1 , · · · , In definidos por
Ii = {j ≤ n : Ai ∩ Bj 6= ∅}

8. Recorde-se que α0 (G) designa o número de arestas num emparelhamento

máximo de G. Mostar que
a) α0 (G) ≤ n − χ(G);
b) se G não tem triângulos então α0 (G) = n − χ(G).
Sugestão: Na alı́nea a), considerar um emparelhamento máximo de G
e verificar que podemos colorir G com n − α0 (G) cores. Na alı́nea b)
começar por verificar quantos vértices pode ter um conjunto estável em
(G).
10. Fixamos um inteiro ı́mpar n = 2m + 1 e definimos o grafo bipartido
G[X, Y ] do seguinte modo:

X = {A ⊂ [n] : |A| = m}, Y = {B ⊂ [n] : |B| = m + 1};

A ∈ X e B ∈ Y são adjacentes se A ⊂ B.

a) Determinar o número de vértices e de arestas de G[X, Y ];

b) Aplicar o Teorema de Hall para mostrar que o grafo admite um em-
parelhamento perfeito.
11. Mostrar que se uma árvore T tem no máximo um emparelhamento per-
feito e que, se o tiver, então, para cada v ∈ VT , T \ v é uma floresta com
exactamente uma componente de ordem ı́mpar.
12. Aplicar a demonstração do Teorema de Berge para provar que se M é
um emparelhamento de G, existe um emparelhamento máximo M 0 que
cobre todos os vértices cobertos por M .

10
1.2 Emparelhamentos com prioridades ou o “problema dos casamentos”

Vimos já que se um grafo bipartido G[X, Y ] satisfaz a condição do Teorema

de Hall para X, existe um emparelhamento que cobre todos os elementos de
X. No entanto, em muitas situações de aplicação deste resultado, o problema
é mais complexo.

Considere-se, por exemplo, a situação em que n pessoas se candidatam a

m vagas; se todos os candidatos concorrem a todas as vagas, a condição para
que todos fiquem colocados é simplesmente |X| ≤ |Y |. Mas é possı́vel que
cada pessoa ordene as vagas numa lista de acordo com as suas preferências;
do mesmo modo, podemos supôr que as empresas ou instituições com vagas a
preencher ordenam os candidatos de acordo com as suas próprias preferências.
O problema de saber como preencher as vagas de modo a satisfazer o mel-
hor possı́vel os desejos dos candidatos, ou os das empresas, ou ambos, ficou
conhecido, por razões óbvias, como o problema dos casamentos. Nessa inter-
pretação, bastante fantasista, cada um de um conjunto X de rapazes e cada
uma de um conjunto Y de raparigas (todos heterosexuais e monogâmicos!)
ordena os elementos do sexo oposto por ordem de preferência e mantém essa
ordem ao longo do tempo; supôe-se igualmente que todos preferem estar
“emparelhados“ do que sózinhos.

Representamos os vértices masculinos por letras maiúsculas e os vértices

femininos por letras minúsculas, sem qualquer intensão discriminatória. Convém,
aliás, sublinhar que toda esta interpretação tem carácter meramente recre-
ativo, não envolvendo, obviamente, qualquer juı́zo de valor sobre os padrões
culturais nela incluı́dos; o autor destas linhas não assume evidentemente qual-
quer responsabilidade pela estabilidade e felicidade dos casamentos organiza-
dos de acordo com os resultados que se seguem...

Limitamo-nos, para maior simplicidade, ao caso em que |X| = |Y | e em que

todos os rapazes ordenam todas as raparigas e vice-versa. O nosso objectivo
é estabelecer um emparelhamento estável: diremos que um emparelhamento
(ou casamento) é estável se não contém pares Ab e Ba em que A e a se pre-

11
firam aos seus pares respectivos. Os matemáticos e economistas americanos
Gale e Shapley apresentaram em 1962 a solução deste problema, mostrando
que existe um algoritmo que tem como resultado um casamento estável.
A aplicação do algoritmo na nossa interpretação reproduz as regras sociais de
norma na sociedade vitoriana: cada rapaz propõe casamento à rapariga da
sua preferência que não o rejeitou até aı́, e cada rapariga aceita a proposta
do seu pretendente favorito. Em termos mais formais, podemos representar o
algoritmo como uma sucessão de passos em que nos passos ı́mpares os rapazes
fazem as suas propostas e nos passos pares as raparigas fazem a sua escolha.

Eis um exemplo muito simples: nos quadros seguintes apresentam-se as lis-

tas de preferências, seguindo-se depois a descrição da aplicação do algoritmo.
Representamos uma proposta como A ? a e o resultado de uma aceitação
como A - a. Nas linhas pares incluı́mos sempre os casais formados em passos
anteriores e que se mantêm, para facilitar a visualização.
A- a b c d e a- C E B D A

B- c a e b d b- B E D A C

C- a d c b e c- D A E B C

D- a b c e d d- D E A B C

E- c a b d e e- E A D B C

1. A ? a , B ? c , C ? a , D ? a , E ? c
2. C - a , E - c
3. A ? b , B ? a , D ? b
4. C - a , D - b , E - c
5. A ? c , B ? e

12
 6. A - c , B - e , C - a , D - b c troca E por A;
7. E ? a
8. A - c , B - e , C - a , D - b a rejeita a proposta, logo nada se altera;
9. E ? b
10. A - c , B - e , C - a , E - b b troca D por E;
11. D ? c
12. B - e , C - a , D - c , E - b c troca A por D;
13. A ? d
14. A - d , B - e , C - a , D - c , E - b todos estão emparelhados;
15. celebram-se os cinco casamentos!
Alguns factos são de verificação imediata:
• No caso de n rapazes e m raparigas, o algoritmo termina no máximo em
2nm passos, e se n ≤ m termina com a criação de n pares;
• depois de comprometido, cada rapaz só muda para pior (do seu ponto
de vista!) e, se n > m, só não termina emparelhado se for rejeitado por
todas as raparigas;
• depois de se comprometer, uma rapariga nunca fica sem par e só muda
para melhor (mais uma vez, de acordo com o seu ponto de vista...);

Teorema 1.18 : O algoritmo de Gale-Shapley produz um emparelhamento

estável.

Demonstração 1.19 : Com as observações anteriores, resta provar que o

emparelhamento é estável. Suponhamos que X e y não terminam emparelha-
dos; isso só acontece se X nunca chegou a propor-se a y ou se y rejeitou X;

13
no primeiro caso, X está emparelhado com alguém que prefere a y, enquanto
que no segundo caso é y que está emparelhada com alguém acima de X na
sua lista. Num caso ou noutro a condição de estabilidade do emparelhamento
está satisfeita.

A observação seguinte permite-nos comparar o resultado desta aplicação

do algoritmo com outros possı́veis emparelhamentos estáveis (com as mesmas
listas de preferências, bem entendido).

Lema 1.20 : Se algum y rejeitou algum X no decurso da aplicação do al-

goritmo, então X e y não ficam emparelhados em qualquer emparelhamento
estável.

Demonstração 1.21 : usamos indução nos passos do algoritmo: supon-

hamos que estamos no primeiro passo do algoritmo em que algum y rejeitou
algum X, existindo um emparelhamento estável M em que X e y estão em-
parelhados.
Isso acontece se
• ou y está emparelhado com T, acima de X na sua lista;
• ou y estava emparelhada com X e rejeita-o por receber uma proposta de
um T acima de X na sua lista.
Em qualquer caso, existe um T acima de X na lista de preferências de y;
mas no suposto emparelhamento M , temos o par X - y e portanto T estará
emparelhado com alguma z, que tem que estar acima de y na lista de pre-
ferências de T, caso contrário M não é estável.
Voltando à aplicação do algoritmo, se T não está emparelhado com z, é porque
foi rejeitado por z num passo anterior, contradizendo a nossa hipótese de que
y rejeita X era a primeira ocorrência desse tipo.

Este resultado, juntamente com as observações anteriores, leva-nos a con-

cluir que nenhum outro emparelhamento estável pode melhorar a situação de

14
qualquer dos proponentes X, ou seja, o resultado do algoritmo é o melhor
emparelhamento estável para os proponentes.
Por outro lado, se o algoritmo produz o par X - y também não pode existir
um emparelhamento estável em que y está emparelhada com um S abaixo de
X na sua lista de preferências, pois nesse emparelhamento X teria que estar
emparelhado com uma z acima de y na sua lista, caso contrário o emparel-
hamento não seria estável. Ora isso contradiz a conclusão anterior. Portanto
o resultado do algoritmo é o pior possı́vel para as raparigas (os aceitantes
de propostas), no sentido em que noutro emparelhamento estável qualquer
nenhuma poderia piorar de situação.

É possı́vel generalizar o problema dos emparelhamentos estáveis em grafos

bipartidos ( listas de preferências incompletas, por exemplo ) e adaptar o
algoritmo a essas situações. Por outro lado, podem considerar-se problemas
como o de emparelhamentos com preferências em grafos não bipartidos, para
os quais não existe, em geral, uma solução estável.

15