MO405 - Questão para a prova oral

Número: 081

Enunciado: Considere dois grafos G e H, onde H=G-e (H é obtido pela remoção de uma aresta e de G). Quantas das afirmações abaixo são falsas?

(I) Se G é um K₅,então H é planar.

(II) Se G é perfeito, então H é perfeito.
(III) Se G é planar, então H é planar e o dual de H é G.e (contração da aresta e em G).

a) 3

b) 2

c) 1

d) 0

 

e) NDA