2025/05/01 by Zhen Liu, Liu, Zhen, Qinghou Zeng +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2505.00523
Answering a question of Erdős and Hajnal, Chen and Ma proved that for all \(n≥600\) every graph with \(2n + 1\) vertices and at least \(n2 + n+1\) edges contains two vertices of equal degree connected by a path of length three. The complete bipartite graph Kn,n+1 shows that this edge bound is sharp. In this paper, we develop a novel approach to handle graphs with large equal degrees, which enables us to establish the result for all n≥2, thereby fully resolving the problem posed by Erdős and Hajnal.