The study is based on the important role of graph theory in the teaching of physical dance and aesthetic education, integrating the concept of graph theory into it and designing the training path of physical dance and aesthetic education based on graph theory. Taking two classes in a university as the research object, the teaching experiment is conducted to compare their physical quality and course performance after the experiment, and the aesthetic education evaluation index system is constructed, and the index weights are measured using the combination assignment method to carry out the comprehensive scoring. After the experiment, the students improved in physical quality, course grades and aesthetic effect, and as far as the students of traditional teaching class are concerned, the experimental students improved in course grades and aesthetic effect by 18.17% and 7.52% respectively. The teaching practice of integrating the concept of graph theory and the curriculum of physical education dance and aesthetic education not only embodies the concept of cross-disciplinary teaching, but more importantly improves the physical quality, physical education dance level and aesthetic effect of students in colleges and universities, and provides a reference for the teaching reform of physical education dance and aesthetic education in colleges and universities.