2024-127

Considere o seguinte grafo simples $G$:

$$V(G)=\{a,b,c,d,e,f,g\}$$

$$E(G)=\{ab,ac,ad,bc,be,cd,cf,dg,ef,fg\}$$

Se o grafo $G$ representa um mapa de cidades onde vértices adjacentes compartilham uma fronteira, determine o número mínimo de cores $\chi (G)$ que podem ser utilizadas para colorir $V(G)$,  garantindo que vértices adjacentes tenham cores distintas.

a) $\chi (G)=6$

b) $\chi (G)=5$

c) $\chi (G)=4$

d) $\chi (G)=3$

e) NDA

Ideia original de: Glaymar A. França