This paper seeks to show a proposal of inclusion of elementary topics of Graphs theory, with emphasis in Eulerian graphs, on basic school. We begin with an introduction to this theory highlighting some important definitions which underpin this paper beyond relevant theoretical conceptions to deal with the specific issue of Eulerian graphs. In addition, some suggestions of activities on the subject, which can be applied in any level of basic education, from Elementary to High School, are presented with the intention of help teachers interested in using new proposals on their pedagogical practice. So they can use this material as a motivating resource for new constructions or just adapt it, change it and/or use it in his classroom routine. Some of the proposed activities were applied with seventh year students from a public school of Rio de Janeiro and the methodology and evaluation of this application are also described on this present work. Therefore it is intended to promote a reflection about new strategies that increase the teaching-learning process of Mathematics in the searching for more autonomy and more meaningful mathematical education.