The need to develop consistent theoretical frameworks for the teaching and learning of discrete mathematics, specifically of graph theory, has attracted the attention of the researchers in mathematics education. Responding to this demand, the scope of the Van Hiele model has been extended to the field of graphs through a proposal of four levels of reasoning whose descriptors need to be validated according to the structure of this model. In this paper, the validity of these descriptors has been approached with a theoretical analysis that is organized by means of the so-called processes of reasoning, which are different mathematics abilities that students activate when solving graph theory problems: recognition, use and formulation of definitions, classification, and proof. The analysis gives support to the internal validity of the levels of reasoning in graph theory as the properties of the Van Hiele levels have been verified: fixed sequence, adjacency, distinction, and separation. Moreover, the external validity of the levels has been supported by providing evidence of their coherence with the levels of geometrical reasoning from which they originally emerge. The results thus point to the suitability of applying the Van Hiele model in the teaching and learning of graph theory.