Problem #816: Let $G$ be a graph with $2n+1$ vertices and $n^2+n+1$ edges

---

Progress

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}$.