MO405 - Questão para a prova oral

Número:


Enunciado: Seja G um grafo, avalie as seguintes alternativas:


a) Para qualquer k > 0, todo G k-regular tem um matching perfeito.


b) Se n(G) for ímpar, G não possui um matching perfeito.


c) O tamanho de um matching de G é igual à metade do número de arestas de G


d) Seja G um n-path, o β(G) = n/2


e) NDA


Ideia original de: Rafael Werneck