O presente trabalho busca apresentar uma proposta de inclusão de tópicos elementares da teoria de Grafos, com destaque para os Grafos Eulerianos, na educação básica. Iniciamos com uma introdução a essa teoria destacando algumas definições importantes que fundamentam o trabalho além de concepções teóricas relevantes para tratar da questão específica dos Grafos Eulerianos. Posteriormente, algumas sugestões de atividades sobre o tema, que podem ser aplicadas em qualquer nível da educação básica desde o Ensino Fundamental até o Ensino Médio, são apresentadas com o intuito de auxiliar e inspirar o professor desse segmento que esteja interessado em utilizar novas propostas na sua prática pedagógica. Assim, esse profissional pode se valer do presente trabalho como um recurso motivador para novas construções ou simplesmente adaptá-lo, alterá-lo e/ou utilizá-lo na realidade da sua sala de aula. Algumas das atividades propostas foram aplicadas com alunos do sétimo ano de uma escola pública do Rio de Janeiro e a metodologia e avaliação desta aplicação encontram-se também descritas no presente estudo. Desta forma, pretende-se promover uma reflexão sobre novas estratégias que incrementem o processo de ensino-aprendizagem da Matemática na busca de uma educação Matemática mais autônoma e mais significativa.