2024-177

Considere o grafo $G$ com os seguintes vértices e arestas:
$$V(G)=\{A,B,C,D,E,F\}$$

$$E(G)=\{(A,B),(A,C),(A,D),(B,C),(B,D),(C,D),(C,E),(D,E),(D,F),(E,F)\}$$

Qual das alternativas a seguir é correta?

a) $G$ é planar, possui número cromático 3, e contém um ciclo hamiltoniano: $A$-$B$-$C$-$D$-$E$-$F$-$A$.

b) $G$ não é planar, possui número cromático 4, e não contém um ciclo hamiltoniano.

c) $G$ é planar, possui número cromático 3, e não contém um ciclo hamiltoniano.

d) $G$ é planar, possui número cromático 4, e contém um ciclo hamiltoniano: $A$-$D$-$C$-$E$-$F$-$B$-$A$.

e) N.D.A.

ideia original de: Glaymar A. França