Erdős和Hajnal关于端点同度路径的问题

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

摘要 Abstract

我们解决了Erdős和Hajnal在1991年提出的一个问题,证明了对于所有$n \geq 600$,每个$(2n+1)$顶点且至少有$n^2 + n + 1$条边的图中,存在两个具有相同度数的顶点,它们由一条长度为三的路径连接。完全二分图$K_{n,n+1}$表明该边界的数量是尖锐的。我们进一步研究了偶数阶图的类似结果,并探讨了若干相关的极值问题。

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.