Erdős Problem #816

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}\). For \(n = 1\) the graph is a triangle, which contains no path of length \(3\), so we assume \(n \geq 2\).