MO405 - Questão para a prova oral (Extra)

Número:

Enunciado: Sabendo que G é um grafo simples que possui como fechamento (closure) o grafo K₅, analise as afirmações abaixo e assinale a alternativa correta.

  

I - G é Hamiltoniano.
II - A conectividade de G é maior ou igual ao seu número de independência, ou seja: κ(G) ≥ α(G).
III - O grau mínimo de G é maior ou igual ao seu número de vértices dividido por 2, ou seja: δ(G) ≥ n(G)/2.
IV - G possui um ciclo gerador de tamanho 6.

a) Apenas a afirmação I está correta.
b) Apenas a afirmação IV está incorreta.
c) As afirmações II e IV estão incorretas.
d) Todas as afirmações estão corretas.
e) N.D.A.


Ideia original de: Leandro Teófilo