2025/03/25 by Chen, Kaizhe, Ma, Jie · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.19569
We address a problem posed by Erdős and Hajnal in 1991, proving that for all n ≥ 600, every (2n+1)-vertex graph with 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 demonstrates that this edge bound is sharp. We further establish an analogous result for graphs with even order and investigate several related extremal problems.