A problem of Erdős and Hajnal on paths with equal-degree endpoints

Abstract

We address a problem posed by Erdős and Hajnal in 1991, proving that for all $n\ge 600$, every $(2n+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.

15 pages