(POSCOMP 2013, questão 37) Seja G o grafo representado pela �gura a seguir. Assinale a alternativa que apresenta, corretamente, o número cromático...

O número cromático de um grafo é o menor número de cores necessárias para colorir todos os vértices do grafo de forma que dois vértices adjacentes não tenham a mesma cor. Analisando o grafo apresentado na questão, podemos perceber que existem dois vértices adjacentes, ou seja, que possuem uma aresta que os conecta. Portanto, é necessário pelo menos duas cores para colorir o grafo. No entanto, podemos perceber que não é possível colorir o grafo com apenas duas cores, pois existem três vértices que são adjacentes entre si. Portanto, o número cromático do grafo é 3. A alternativa correta é a letra A.