For every n at least 2, every (2n+1)-vertex graph with at least n^2+n+1 edges contains two equal-degree vertices joined by a path of length three, with K_{n,n+1} as the unique extremal graph.
A problem of Erd\H{o}s and Hajnal on paths with equal-degree endpoints
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We address a problem posed by Erd\H{o}s and Hajnal in 1991, proving that for all $n \geq 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.
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
A complement of the Erd\H{o}s-Hajnal problem on paths with equal-degree endpoints
For every n at least 2, every (2n+1)-vertex graph with at least n^2+n+1 edges contains two equal-degree vertices joined by a path of length three, with K_{n,n+1} as the unique extremal graph.