This article presents research on students' understanding of basic concepts in Graph Theory. Students' understanding is analyzed through the lens of the theoretical framework of reducing abstraction (Hazzan, 1999). As it turns out, in spite of the relative simplicity of the concepts that are introduced in the introductory part of a traditional Graph Theory course, some students exhibit ways of thinking that indicate a reduction of the level of abstraction. The importance of this study is derived from the importance of graph algorithms in any computer science curriculum and the centrality of the concept of abstraction in computer science education. (Contains 7 figures.)