Erdős Problem #816
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
For n>=600, a graph on 2n+1 vertices and at least n²+n+1 edges has a SIMPLE path of exactly three edges whose two endpoints have the same degree IN THE ORIGINAL GRAPH. A 3-edge walk with repeated vertices is not enough; endpoints are not required to be adjacent.
A small example
In K_{n,n+1}, any 3-edge path begins in one bipartition class and ends in the other; endpoint degrees n+1 versus n, so it cannot have equal-degree endpoints. For n=2, K2,3 has five vertices and six edges; its 3-paths have endpoint degrees 3 and 2. This finite structural witness verifies sharpness logic but not n>=600 positive theorem.
What is known
Maintained #816 and independently read original published Kaizhe Chen–Jie Ma, A problem of Erdős and Hajnal on paths with equal-degree endpoints, JCTB 179 (July 2026), 1–18, DOI 10.1016/j.jctb.2026.01.006, Theorem 2: for n>=600, the unique graph on 2n+1 vertices with at least n²+n edges lacking such a path is K_{n,n+1}. It has exactly n²+n edges and is the sharp exception. The original published theorem statement is independently identified, not full proof kernel-replayed.
The sharp theorem identifies the entire exception class: when \(n\geq600\), among graphs on \(2n+1\) vertices with at least \(n^2+n\) edges, the only graph without equal-degree endpoints of a simple three-edge path is \(K_{n,n+1}\). The latter has exactly \(n^2+n\) edges, and each three-edge path crosses between its two degree classes. Raising the edge count by one removes the exception.
The published theorem can be separated into its threshold and exception:
If no simple three-edge path has equal-degree endpoints, then \(G\) must be \(K_{n,n+1}\). Conversely, in \(K_{n,n+1}\) any path of odd length crosses from one part to the other, where the degrees differ. Therefore one additional edge above \(n^2+n\) rules out the sole exception.
GCL's current state
The authenticated original RESULT/1 source return records SOURCE_LOCK_READY and preserves its issue-bound mathematical source observations. This explanatory article is REVIEWED under the exact-hash EC-BULK-005-R6 editorial transaction, subject to the protected merge of PR #2676. Its original source-audit status is retained. Editorial acceptance and public MathJax validation do not certify any original research theorem, external Lean file, or complete historical proof.
Unclosed mathematical proof/source qualifications: CHEN_MA_2026_FULL_PROOF_NOT_REPLAYED; N_GE_600_ESSENTIAL.
What remains
Exact path enumerator on K2,3 and K2,3 plus one intra-part edge, verifying all four vertices distinct and degrees from the original graph. Check Chen–Ma 2026 printed Theorem 2 quantifiers and uniqueness; do not generalize to n<600.
For mathematical proof certification, the complete primary argument and any external formalization must undergo separate independent replay. The bounded finite calculation is recorded in the governed R6 fixture; editorial approval does not discharge the outstanding research obligations.
Sources and claim boundaries
- Erdős problem #816, maintained LaTeX and original authenticated source return, checked 14 October 2026.
- Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The source comment contains original bibliography and limits of direct proof inspection.
- Editorial decision: exact-hash reviewed explanatory article, protected R6 transaction. Mathematical theorem proof / external Lean certification: NOT CLAIMED. The original SOURCE_LOCK_READY return, primary-source attribution, and proof-review holds remain.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2087 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.