MO405 - Questão para a prova oral

Número: 078

Enunciado: Considere as afirmações a seguir, referentes a coloração de vértices.

I) Todo grafo estrela é crítico.

II) Todo grafo Kn é n-crítico e, portanto, é (n-1)-aresta-conexo.

III) O grafo Kx ∨ Cy, com x>0 e y>0, é crítico.

Podemos dizer que:

a) Apenas  I é verdadeira.
b) Apenas I e II são verdadeiras.
c) Apenas II é verdadeira.
d) Apenas II e III são verdadeiras.
e) NDA

Ideia original de: Vitor Afonso