MO405 - Questão para a prova oral

Número: 112

Enunciado: Seja G uma árvore e H um ciclo. Das afirmações abaixo, quantas são FALSAS?

i) O produto cartesiano entre G e H é um grafo perfeito.
ii) Todo subgrafo próprio de H é perfeito.

iii) Se incluirmos uma aresta em G, o grafo obtido será imperfeito.
iv) Se incluirmos ⌈n(H)/2⌉ arestas em H, mantendo-o simples, o grafo obtido será perfeito.

a) 1

b) 2

c) 3

d) 4

e) NDA