Este artigo é resultado de pesquisa de Iniciação Científica de caráter qualitativo realizada como estudos de casos a partir da produção e utilização de diferentes atividades didáticas para abordagem de Teoria dos Grafos no Ensino Médio. Apresentamos e discutimos possibilidades metodológicas para abordagem do tema Grafos no Ensino Médio. As discussões são orientadas à luz da História da Matemática, da Resolução de Problemas, do Uso de Materiais Manipulativos e da Modelagem Matemática, com atividades pertencentes a cada uma destas metodologias. Esperamos que os resultados das atividades realizadas apontem para a possibilidade, relevância e potencialidade da Teoria dos Grafos nas aulas de matemática do Ensino Médio.