We address a problem posed by Erdős and Hajnal in 1991, proving that for all n ≥ 600 , every ( 2 n + 1 ) -vertex graph with at least n 2 + n + 1 edges contains two vertices of equal degree connected by a path of length three. The complete bipartite graph K n , n + 1 demonstrates that this edge bound is sharp. We further establish an analogous result for graphs with even order and investigate several related extremal problems.
Chen et al. (Thu,) studied this question.