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