PROVED
This has been solved in the affirmative.
Let $G$ be a graph with $2n+1$ vertices and $n^2+n+1$ edges. Must $G$ contain two vertices of the same degree which are joined by a path of length $3$?
A problem of Erdős and Hajnal. The example of $K_{n,n+1}$ shows that this fails if we only have $n^2+n$ edges.
This is true, and was proved by Chen and Ma
[ChMa25], who prove the stronger statement that, provided $n\geq 600$, all graphs with $2n+1$ vertices and at least $n^2+n$ edges contain two vertices of the same degree joined by a path of length $3$, except $K_{n,n+1}$.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #816, https://www.erdosproblems.com/816, accessed 2025-11-15
