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$ ?

Second statement

Let $G$ be a graph with $2n+1$ vertices and $n^2+n+1$ edges, where $n\geq 2$ . Must $G$ contain two vertices of the same degree which are joined by a path of length $3$ ?

Source: erdosproblems.com/816

Graph theory

Wiki page

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

PROVED, the site's label, resting on the commentary's credit to [ChMa25], whose theorem needs $n\ge600$ . The corrected Statement is proved for $n\ge600$ by Theorem 2 of [ChMa25] (J. Combin. Theory Ser. B 179 (2026), 1--18; refereed; cited from arXiv v1), in the stronger form that $K_{n,n+1}$ is the only graph with $2n+1$ vertices and at least $n^2+n$ edges without such a pair; it is recorded as an accepted partial claim on Chen and Ma's claim page (2025). The preprint [LiZe25] (arXiv:2505.00523v2, August 2025) states the same theorem for every $n\ge2$ (its Theorem 1.3), which is the whole corrected Statement, and presents it as resolving the question completely; no journal record and no independent review of it was found on 2026-09-18, its proof (pp. 2--14) is unread, and it is recorded as the pending full claim on Liu and Zeng's claim page (2025). The derived standing is therefore claimed, proved: the range $3\le n\le599$ rests on [LiZe25] alone, and the case $n=2$ is also checked by hand below. The site's wording, which also admits $n=1$ , fails there (see Notes).

Notes

The site's wording leaves $n$ free, so it includes $n=1$ , where it is false. A path of length $3$ is a path with three edges and four distinct vertices: this is the reading under which the site's own example works ( $K_{n,n+1}$ has $n^2+n$ edges, its equal-degree vertices lie on one side, and a path with an odd number of edges joins the two sides), and it is the reading of [ChMa25] (proof of Lemma 4, p. 3: " $uu_1vw$ is a path of length three joining $u$ and $w$ "). At $n=1$ the graph has $3$ vertices and $3$ edges, so it is $K_3$ ; its three vertices all have degree $2$ , but a graph on three vertices contains no path with four vertices, so no two of them are joined by a path of length $3$ , and the answer is no. The check needs no source. The change inserts "where $n\geq 2$ ", which excludes exactly $n=1$ , the one value at which, because of its size, no graph can meet the conclusion; it is the corpus's own correction. The first value above it, $n=2$ , holds for all four graphs (checked in the Current assessment). No source of higher rank supplies a range: Erdős's [Er91] was not read, and the statements of his question as Problem 1 of [ChMa25] (p. 1) and Problem 1.1 of [LiZe25] (p. 1) carry no range on $n$ , so the missing range is not the site's alone; the site's commentary gives the range $n\ge600$ of Chen and Ma's theorem, which is a theorem's hypothesis and not the form. The form follows from the size of the failing instance alone, not from the range of any theorem; the formal-conjectures statement file states the same range $n\ge2$ . Results about the site's wording, credited and never counted: the failure at $n=1$ is this corpus's own check, first recorded on this page on 2026-09-18; the formal-conjectures statement file, added on 2026-09-20, notes that at $n=1$ the graph is a triangle with no path of length $3$ ; and the docstring of Boris Alexeev's Lean development (commit of 15 September 2026) names $K_3$ as a counterexample at $n=1$ . The page's standing judges the corrected Statement.

Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley (1991), 397--406. The origin; [ChMa25] cite it as their [4] for Problem 1, and [LiZe25] as their [3]. The passage was not read; Erdős's wording is known only through the restatements in [ChMa25] and [LiZe25].
ChMa25: Chen, K. and Ma, J., A problem of Erdős and Hajnal on paths with equal-degree endpoints. J. Combin. Theory Ser. B 179 (2026), 1--18, doi:10.1016/j.jctb.2026.01.006 (issued July 2026; Crossref record of 2026-09-18; the site's reference text gives "arXiv:2503.19569 (2025)"); arXiv:2503.19569 (v1, 25 March 2025, 15 pp.; the only arXiv version, with no journal reference in the arXiv record). Problem 1 and the attribution, p. 1; Theorem 2, the non-monotonicity remark and Theorem 3, p. 2; the proof of Theorem 2, pp. 2--11; the remark on the constant $600$ , p. 11; Section 4 with $p_\ell(n)$ , Theorems 12--13, Conjecture 14 and Problem 15, pp. 13--15. Library home: Chen 2025; paged at Chen 2025, Theorem 2.
LiZe25: Liu, Z. and Zeng, Q., A complement of the Erdős--Hajnal problem on paths with equal-degree endpoints. arXiv:2505.00523 (v1 1 May 2025; v2 4 August 2025, 14 pp.); Theorem 1.3, p. 1; Theorem 1.5, p. 2. A preprint with no journal record found (Crossref, Semantic Scholar, 2026-09-18); v2 on its card Liu and Zeng 2025; not cited by the site.
LiZe26: Liu, Z. and Zeng, Q., Paths of length five with equal-degree endpoints. arXiv:2604.11664 (v1, 13 April 2026); abstract only. [ZWL26] Zhao, X., Wang, Y. and Lu, M., A generalization of Erdős--Hajnal problem on paths with equal-degree endpoints. arXiv:2605.03825 (v1, 5 May 2026); abstract only. [AABPT26] Attwa, Y., Azócar Carvajal, M., Boyadzhiyska, S., Pierron, T. and Taraz, A., The density of graphs with no $\ell$ -path connecting equal-degree vertices: a short proof. arXiv:2605.09798 (v1, 10 May 2026); abstract only. [CLZ26] Chen, K., Liu, Z. and Zeng, Q., Paths of even length with equal-degree endpoints. arXiv:2607.04368 (v1, 5 July 2026); abstract only. Leads on the variants, recorded below; none concerns the statement.

Problem 816

Second statement

Status

Notes

Proof claims

Discussion