Skip to content

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:

\[ |V(G)|=2n+1,\quad e(G)\geq n^2+n,\quad n\geq600. \]

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.

Back to catalogue · Compendium introduction