O Problema do Caixeiro Viajante (PCV) surgiu em meados de 1930. Considerado um dos grandes problemas do milênio relativo à Teoria dos Grafos ele é de natureza NP-Difícil com inúmeras aplicações na ciência da computação, engenharia, matemática e áreas correlatas. O PVC trata de determinar o caminho mais curto possível para viajar dentre n cidades passando por elas apenas uma vez e retornando ao ponto inicial. Embora seja um problema em aberto, a questão a ser trabalhada é acessível aos alunos do ensino básico. Neste trabalho, as irmãs Juli e Érika abordam dois métodos para inserir um problema ainda sem solução, para o público do ensino básico e relacioná-lo às sugestões das habilidades e competências da BNCC. O jogo intitulado Tabuleiro do Caixeiro Viajante respaldou a proposta de metodologia a ser aplicada nos anos iniciais e finais do ensino fundamental. Todavia, o jogo de aplicativo Pokémon Go subsidiou a proposta de aplicação do PCV nas turmas de ensino médio. Ambas as propostas foram provenientes de pesquisas bibliográficas com referências disponíveis em periódicos e livros a respeito da teoria dos grafos. Além disso, este trabalho tem como produto uma cartilha educacional que pode servir como instrumento didático, uma vez que o formato facilita o acesso às ferramentas e conhecimentos matemáticos utilizados durante o desenvolvimento da pesquisa.