MO405 - Questão para a prova oral

Número: 042

Enunciado:  Considere que o caminho P = ( (2,6), (6,1), (1,7), (7,3), (3,9), (9,5), (5,8) ) é alternante para um emparelhamento M = ( (6,1), (7,3), (9,5) ) de um grafo bipartido G com nove vértices. Podemos afirmar que:

a) | M | = α'(G)

b) | P ∆ M | = α'(G)

c) | P | + | M | = α'(G)

d) | M | = α(G)

e) NDA