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.
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.
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
Nenhum comentário:
Postar um comentário