Grafos e número cromático

Prova de Matemática - Canguru Matemático sem Fronteiras JÚNIOR 2019 / 10º - 11º anos

25. Na figura ao lado temos um grafo com 16 vértices e algumas arestas que os unem.
     Uma formiga está no vértice assinalado com A. 
     Ela pode movimentar-se ao longo do grafo do seguinte modo: em cada movimento pode deslocar-se para um vértice vizinho seguindo por uma das arestas que os une. Depois de 2019 movimentos em qual dos vértices P, Q, R, S ou T pode estar a formiga?

 

     (A) Só no P, R ou S, mas não no Q, nem no T 
     (B) Só no P, R, S ou T, mas não no Q
     (C) Só no Q 
     (D) Só no T
     (E) Em qualquer um desses vértices

Solução: (C) Só no Q 

exercício nº 25 Canguru Matemático 2019 Nível J - 10º-11º anos
========================================
Neste vídeo é resolvido o exercício nº 25 da prova escolar Canguru Matemático sem Fronteiras JÚNIOR 2019/10º-11º anos, e a 
resolução deste problema vai ter por base conceitos:

► associados a grafos
► e número cromático de um grafo





Link do vídeo:  https://youtu.be/My02KBJTsXY

Caminho mínimo de A para T ---> 2 ---> par ---> não serve
Caminho mínimo de A para P ---> 4 ---> par ---> não serve
Caminho mínimo de A para S ---> 4 ---> par ---> não serve
Caminho mínimo de A para R ---> 4 ---> par ---> não serve

Caminho mínimo de A para Q ---> 5 ---> ímpar ---> OK