MO405 - Questão para a prova oral

Número:

Enunciado:
Considere um grafo bipartido G e um emparelhamento máximo M. Podemos afirmar que:

a) Todo caminho M-alternante possui as duas extremidades saturadas por M.

b) M é o único emparelhamento máximo em G.

c) Todo emparelhamento maximal possui o mesmo tamanho de M.

d) Não existem caminhos M-aumentantes em G.

e) NDA