We use a representation for the spanning tree where a parent function maps non-root vertices to vertices. Two spanning trees are defined to be adjacent if their function representations differ at exactly one vertex. Given a graph $G$, we show that the graph $H$ with all spanning trees of $G$ as vertices and any two vertices being adjacent iff their parent functions differ at exactly one vertex is connected.

The application of technologies such as big data, mobile Internet, artificial intelligence and so on has triggered a major change in the field of education and promoted the classroom reform in colleges and universities. Taking deep learning theory as the research perspective, this paper constructs a college English teaching model based on deep learning, and applies the model to actual teaching practice, with a view to promoting students’ English learning level and enhancing their intercultural communication ability. Among them, the K-means algorithm improved by the whale optimization algorithm is also used to cluster and stratify the English proficiency of students in a class to illustrate the specific application of deep learning in English teaching. The results classified the sample students into four categories, A, B, C and D. The English level of students in category A is the highest and the largest, accounting for 35.56%, and teachers can design differentiated teaching based on the results of student stratification. After carrying out the experiment of the teaching model, the practicing students’ English scores improved by 4.01%, and at the same time, they gained 18.87%~28.45% and 18.82%~39.01% of competence in the personal domain and the communicative domain, respectively, which confirms the effect of the constructed English teaching model on the enhancement of the students’ English learning level and cross-cultural communicative competence.