1) Dê o número cromático $ \chi(G) $ do grafo a seguir:
A) 2
B) 4
C) 3
D) 6
E) 5

Question

Accepted Answer

O número cromático de um grafo é o menor número de cores necessárias para colorir os vértices do grafo de forma que dois vértices adjacentes não compartilhem a mesma cor.

Para o grafo da imagem, podemos observar que ele possui uma estrutura central que se assemelha a um ciclo de quatro vértices (um quadrado com uma aresta diagonal). Além disso, há um vértice conectado a esse ciclo.

1. Comece colorindo um dos vértices do ciclo com a cor 1.
2. O vértice adjacente a ele no ciclo deve ser colorido com a cor 2.
3. Continue alternando as cores 1 e 2 ao redor do ciclo.
4. O vértice extra conectado ao ciclo pode ser colorido com a cor 3, já que ele está conectado a dois vértices de cores diferentes (1 e 2).

Assim, o número cromático desse grafo é 3.

**Resposta: C) 3**

1) Dê o número cromático do grafo a seguir: A) 2 B) 4 C) 3 ...

Dê o número cromático $\chi(G)$ do grafo a seguir: A) 2 B) 4 C) 3 D) 6 E) 5

Ask a question and receive an answer instantly

1) Dê o número cromático do grafo a seguir: A) 2 B) 4 C) 3 ...

Dê o número cromático χ(G)\chi(G)χ(G) do grafo a seguir: A) 2 B) 4 C) 3 D) 6 E) 5

Ask a question and receive an answer instantly

Dê o número cromático $\chi(G)$ do grafo a seguir: A) 2 B) 4 C) 3 D) 6 E) 5