2024-159

 Considere as seguintes afirmativas:

I) Seja \(G\) um grafo conexo com \(n\) vértices, \(m\) arestas e número cromático 4. Podemos afirmar que \( m \geq 6 \).

II) O grafo abaixo não contém uma subdivisão de \( K_4 \):

III) Se \(G\) é 3-crítico, podemos afirmar que \(G\) é um ciclo ímpar e que todo subgrafo próprio \( H \subseteq G \) é bipartido.

IV) Seja \(G\) um grafo conexo de número cromático \( k \geq 2 \) e que pode ser separado em \(b\) blocos, sendo um desses blocos um grafo caminho. Podemos afirmar que \(G\) é \(k\)-crítico.

Assinale a alternativa CORRETA:

a-) Apenas as afirmativas III e IV estão CORRETAS

b-) Apenas as afirmativas II e IV estão CORRETAS

c-) Apenas as afirmativas I, II e IV estão CORRETAS

d-) Apenas as afirmativas I e III estão CORRETAS

e-) N.D.A.

 

Ideia original de: Gabriel S. Kraszczuk