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\ge 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\ge 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