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

Key Points

• Every (2n + 1)-vertex graph with n ≥ 600 and at least n² + n + 1 edges contains two equal degree vertices, connected by a path of length three.
• The complete bipartite graph Kn,n+1 serves as a sharp example, demonstrating that the found edge bound is tight.
• Graph theories were explored, focusing on structures associated with equal degree endpoints, revealing new patterns in graph connectivity.
• Analogous results were derived for graphs with even orders, further investigating related extremal problems.

Abstract