A complement of the Erd\H{o}s-Hajnal problem on paths with equal-degree endpoints

Qinghou Zeng; Zhen Liu

REVIEW 2 major objections 7 minor 1 cited by

A complement of the Erd\H{o}s-Hajnal problem on paths with equal-degree endpoints

T0 review · 2 major / 7 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every n≥2, K_{n,n+1} is the only graph with n^2+n edges avoiding an equal-degree path of length three; one more edge guarantees such a path.

desk verdict Full-range resolution of the Erdős-Hajnal problem with a solid odd case and a small but real gap in the even case at n=3. read the letter →

arxiv 2505.00523 v2 pith:CKFHKQND submitted 2025-05-01 math.CO

Zhen Liu , Qinghou Zeng This is my paper · ORCID

classification math.CO MSC 05C3505C07

keywords equal-degreeverticespathoflengththreeErdős-Hajnalproblemextremalgraphcompletebipartitedegreesequencecomplementcountingsharpedgebound

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper resolves the Erdős–Hajnal problem on paths with equal-degree endpoints. It proves that for every $n\ge 2$, a graph on $2n+1$ vertices with at least $n^2+n+1$ edges must contain two vertices of the same degree joined by a path of length three. The bound is sharp: the complete bipartite graph $K_{n,n+1}$ has exactly $n^2+n$ edges and no such pair. A companion result shows the analogous even-order extremal graph is $K_{n-1,n+1}$ for every $n\ge 3$, extending results that were previously known only for large $n$.

What carries the argument

The argument is carried by $\beta$, the largest degree that appears at least twice, together with a partition of the vertex set around a pair $u,v$ of degree-$\beta$ vertices into their common neighbourhood $B$, private neighbourhoods $A_u,A_v$, and the residual set $D$. The absence of a three-edge path between equal-degree vertices forbids every edge between $B$ and $A_u\cup A_v$, inside $B$, and between $A_u$ and $A_v$; counting the missing edges in the complement then bounds the total edge count and forces $\beta\le n+1$, with equality characterizing $K_{n,n+1}$.

What would settle it

Run an exhaustive check of all 6-vertex graphs with 8 edges: a graph other than $K_{2,4}$ with no equal-degree pair at distance three would refute Theorem 1.5, and the check would decide whether the unstated characterization in the $n=3$ case of Lemma 3.2 holds.

Watch

Extended reading notes

Core claim

The central discovery is a threshold-and-uniqueness theorem: among all $(2n+1)$-vertex graphs, the only one with at least $n^2+n$ edges in which no two equal-degree vertices lie at distance three is the complete bipartite graph $K_{n,n+1}$. Equivalently, any graph on $2n+1$ vertices with more than $n^2+n$ edges contains two vertices of the same degree connected by a path of length three. The same structure holds for even vertex count: the unique $2n$-vertex graph with at least $n^2-1$ edges and no such path is $K_{n-1,n+1}$. Previously known only for $n\ge600$ and for sufficiently large $n$, the paper removes these thresholds, resolving the Erdős–Hajnal problem completely.

Load-bearing premise

The load-bearing premise is that in the even-order proof, two vertices sharing the largest repeated degree can always be joined by a three-edge path through the two vertices of degrees $2n-1$ and $2n-2$; the required adjacency is not forced by the degree counts, and the $n=3$ equality case is dispatched by an unstated characterization.

Editorial extensions

If this is right

For all $n\ge2$, the Erdős–Hajnal problem is closed: the edge count $n^2+n$ is the exact threshold, and $K_{n,n+1}$ is the unique extremal graph.
Equivalently, any graph on $2n+1$ vertices with $n^2+n+1$ edges contains two vertices of equal degree joined by a path of length three.
The even-order companion holds for all $n\ge3$: $K_{n-1,n+1}$ is the unique extremal graph at $n^2-1$ edges.
The theorem removes the previous $n\ge600$ restriction, so the result holds uniformly from $n=2$ upward.
The paper leaves the odd-length generalisation for $\ell\ge5$ open; its large-equal-degree method is the new tool available for that problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the same $\beta$-partition count is a natural test for the first open odd case $\ell=5$: if the large-equal-degree lemma has an analogue for five-edge paths, then $p_5(2n+1)=n^2+n$ would follow by the same complement-counting route.
The even-order theorem makes the odd/even contrast Chen and Ma conjectured more concrete: at $\ell=3$ the extremal graph is still complete bipartite, so the half-graph construction that lowers the bound for even $\ell\ge2$ must first fail at a longer path length.
A proof-level extension would replace the unstated characterization in the $n=3$ equality case of the even-order argument with an explicit degree-sequence analysis; until then, that case rests on an assertion the paper does not prove.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is that this paper does what it says: extends Chen and Ma's result to all n≥2 for odd vertex count, and to all n≥3 for even vertex count. The odd case, Theorem 1.3, is the main event and it looks sound. The proof borrows Chen and Ma's framework and β parameter, but the treatment of large equal degrees is genuinely new and the counting arguments are checkable. Lemma 2.1 and Lemma 2.2 are clean, and the reduction for n=2,3,4 is explicit. Credit where due: the paper is honest about what comes from Chen and Ma, the reliance on Lemma 2.3 is flagged, and the appendix optimization for Lemma 3.3 is a substantial piece of work in its own right.

The soft spot is in the even case, specifically Lemma 3.2. The reader's worry about the path w1z1z2w2 failing when z1 or z2 is non-adjacent to w1 does not actually hold up: in the even case z1 is universal and z2 has at most one non-neighbor, so one of the two displayed paths does exist. The real problem is different and correctly identified in the stress-test note: the n=3 equality case of the degree-sum bound is dismissed with “the graph G can be characterized” and no characterization is given. That leaves Theorem 1.5 unproved at its base case. Since n=3 is finite, this is very likely fixable by a short case check, but as written it is a genuine gap. There are also minor typos: Lemma 3.4 cites Lemma 2.4 where it should cite Lemma 3.2, and the statement of Theorem 1.5 has a spacing glitch. These are cosmetic.

Overall the central Theorem 1.3 appears correct, and the even case is probably correct modulo the missing n=3 verification. The paper deserves a serious referee, but the referee should insist on seeing the n=3 characterization before accepting. This is exactly the kind of paper where one missing finite case turns a complete proof into a conditional one.

Who is this for? Extremal graph theorists, especially people working on Erdős–Hajnal type degree problems. I would bring it to a reading group and cite it once the even-case gap is patched. My recommendation: send to peer review with a request for revision, not a desk reject.

Referee Report

2 major / 7 minor

Summary. The paper addresses a 1991 problem of Erdős–Hajnal: must every (2n+1)-vertex graph with n²+n+1 edges contain two vertices of equal degree joined by a path of length three? Chen and Ma proved this for n≥600 and showed that K_{n,n+1} is the unique extremal graph with n²+n edges that avoids such a pair. The present paper proves the same characterization for all n≥2 (Theorem 1.3), and the analogous even-vertex theorem for all n≥3 (Theorem 1.5): the unique 2n-vertex graph with at least n²−1 edges avoiding such a pair is K_{n−1,n+1}. The method works in the complement, centered on the parameter β (the largest repeated degree), with complement-counting around a maximum pair (Lemmas 2.1, 2.2), a dichotomy lemma imported from Chen–Ma (Lemma 2.3), and small-n case analyses. The odd-vertex proof appears sound after detailed checking; the even-vertex proof has one unproved finite case in Lemma 3.2 and two lemma statements that are false as written.

Significance. If the missing verification is supplied, Theorem 1.3 fully resolves the Erdős–Hajnal problem, reducing the threshold from n≥600 to n≥2 with a sharp, explicitly characterized extremal graph; Theorem 1.5 extends the even case to all n≥3. The counting arguments are parameter-free and the extremal statements are falsifiable, and the large-equal-degree handling is a genuine complement to the Chen–Ma approach; these are real strengths. The main reservations are the unproved n=3 characterization in Lemma 3.2, which is the sole support for Theorem 1.5 at n=3, and the false statements of Lemmas 2.6 and 3.4; both issues are local and repairable, and neither appears to undermine the correctness of the odd case.

major comments (2)

[§3, Lemma 3.2] The proof of β≥3 for the even case is incomplete. When β≤2, the bound 2e(G)≤2n²−3n+7 contradicts e(G)≥n²−1 for n≥4, but for n=3 it is tight (2e=16). The text then asserts, without proof: 'At this time, the graph G can be characterized and there exists a path of length three with equal-degree endpoints.' This assertion is load-bearing: Lemma 3.3 covers n≥6 and Lemma 3.4 covers n=4,5, while the n=3 case of Theorem 1.5 depends on β≥3, notably through the n=3 subcase of Lemma 3.4. The missing case is finite and should be written out: tightness forces the degree sequence (5,3,2,2,2,2) on six vertices, with the degree-5 vertex universal; the residual degree sequence (2,1,1,1,1) is uniquely realizable, and that realization contains a length-three path joining two degree-2 vertices through the universal vertex. Note also that the final path claim of the lemma (w1z1z2w2 or w1z2z1w2) is in fact valid, since z1 of degree 2n−1 is universal and z2 of degree 2n−2 has at most one non-neighbor; the genuine gap is only the n=3 equality case.
[§2, Lemma 2.6 and §3, Lemma 3.4] Both lemmas are false as stated. Lemma 2.6 asserts Δ≤2n−2 for n∈{2,3,4}; for n=2, the graph K_{2,3} satisfies the ambient hypotheses (five vertices, six edges, no equal-degree pair joined by a path of length three) yet has Δ=3. Lemma 3.4 asserts Δ≤2n−3 for n∈{3,4,5}; for n=3, the graph K_{2,4} satisfies the even-case hypotheses (six vertices, eight edges, no such pair) yet has Δ=4. In each proof the uniqueness of the maximum-degree vertex follows only under the implicit assumption β≤n, which is in force after Lemma 2.2 (respectively Lemma 3.1) has disposed of the extremal case; the extremal graphs themselves are exactly the counterexamples to the stated lemmas. The statements should be corrected by adding the hypothesis β≤n, or by explicitly excluding the extremal graph, so that the lemmas are true as written.

minor comments (7)

[§3, proof of Theorem 1.5, Case 1] The sentence 'which contradicts Lemma 2.3' should cite Lemma 2.5: Lemma 2.3 is the Chen–Ma dichotomy for odd graphs, and it is not contradicted by the displayed configuration (Δ=n+2 satisfies Δ≤n+2). The intended argument is the Lemma 2.5 statement that two common neighbors force distinct degrees.
[§3, Lemma 3.4] In the Δ=2n−1 subcase, the citation 'by Lemma 2.4' should be 'by Lemma 3.2'; Lemma 2.4 is the odd-case bound β≥3, whose even analogue is Lemma 3.2.
[§3, proof of Theorem 1.5, Case 2] The phrase 'If there exists a vertex v3, v1, v2 such that...' is garbled; it should read 'If there exists a vertex v3≠v1,v2 such that...'.
[§3, Cases 1–3] The notation N(v0) is used for both the neighborhood in G and the set of non-neighbors (the complement neighborhood), sometimes within the same case (for example, in Case 1, |N(v0)|=n−3 is a complement count, while the following paragraph uses N(v0) for the neighborhood). Please use N̄(v0) or an explicit 'complement neighborhood' for the latter.
[§2, Lemma 2.6; §3, Lemma 3.4] There are several typos: 'v1 < N(v0)∪{v0}' should be 'v1∉N(v0)∪{v0}' in both lemmas; Lemma 2.6's 'If d(v1),β,' should be 'If d(v1)≠β,'; and Lemma 3.4 contains a stray '1' after 'Lemma 2.5'.
[Appendix, proof of Lemma 3.3] The notation 'A∪N(v0)' in equations (10)–(12) is confusing, since A⊆N(v0); the intended partition is evidently {v0}, the neighborhood N(v0) split into A and B, and the non-neighborhood, with the degree sum over A together with the non-neighborhood being bounded by λ. Please clarify the set partition used in the degree-sum identity.
[§2, Lemmas 2.3 and 2.5] Lemmas 2.3 and 2.5 are quoted from the concurrent Chen–Ma preprint without proofs and without stating their hypotheses in full (for example, the derivation of the condition n≥5 for Lemma 2.3). Since the present paper's main theorems rely on them, restating them completely would make the paper more self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is a direct extremal-graph argument whose only imported tools are external lemmas from Chen and Ma, not assumptions of the theorem being proved.

full rationale

Theorem 1.3 is not derived from itself. The paper defines β as the largest degree occurring at least twice and then carries out degree-sum and neighborhood-counting arguments in Lemmas 2.1, 2.2, 2.4, and 2.6; none of these lemmas assumes the desired uniqueness or extremal conclusion. For n≥5 the argument invokes Lemma 2.3 and Lemma 2.5, both explicitly attributed to Chen and Ma, with stated hypotheses that do not include the target conclusion and with no authors in common with the present paper, so this is external independent support rather than a self-citation chain. The even-order Theorem 1.5 is handled by the same method, with Lemmas 3.1–3.4 proved here and Lemma 3.3 proved in the appendix; no fitted parameter is renamed as a prediction and no quantity is defined in terms of the target quantity. The only notable gap is in Lemma 3.2, where the n=3 tight case is dismissed with 'At this time, the graph G can be characterized and there exists a path of length three with equal-degree endpoints' without supplying the characterization. That is an omitted finite verification and a correctness/completeness risk, but it is not circular: the assertion is used as a step toward a contradiction, not as a restatement of the theorem or of an input. Likewise, Lemma 2.3 is cited rather than reproduced, but its external, parameter-free status keeps the derivation self-contained in the circularity sense. Score 0.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The central claim depends on two external lemmas from Chen and Ma (Lemma 2.3 and Lemma 2.5) that are not proved in this paper. No free parameters or invented entities appear.

assumptions (2)

domain assumption Lemma 2.3 (Chen-Ma): For n at least 5, either beta at least Delta-1 or Delta at most n+1.
Used in the proof of Theorem 1.3 for n at least 5; not proved in this paper, cited from Chen and Ma [2].
domain assumption Lemma 2.5 (Chen-Ma): If u is in N(v) and |N(u) intersect N(v)| is at least 2, then all other vertices in N(v) have degree different from d(u).
Used in Lemmas 2.6 and 3.4; cited from Chen and Ma [2].

how reviews work

0 comments

Cite this review

Pith. "Pith review of A complement of the Erd\H{o}s-Hajnal problem on paths with equal-degree endpoints." pith.science (2026). https://pith.science/paper/CKFHKQND

@misc{pith2026250500523,
  author       = {Pith},
  title        = {Pith review of: A complement of the Erd\Hos-Hajnal problem on paths with equal-degree endpoints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CKFHKQND}},
  note         = {Machine review of arXiv:2505.00523}
}

abstract

Answering a question of Erd\H{o}s and Hajnal, Chen and Ma proved that for all $n\geq600$ every graph with $2n + 1$ vertices and at least $n^2 + n+1$ edges contains two vertices of equal degree connected by a path of length three. The complete bipartite graph $K_{n,n+1}$ shows that this edge bound is sharp. In this paper, we develop a novel approach to handle graphs with large equal degrees, which enables us to establish the result for all $n\ge2$, thereby fully resolving the problem posed by Erd\H{o}s and Hajnal.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Paths of even length with equal-degree endpoints
math.CO 2026-07 accept novelty 6.0 of 10

For every fixed ℓ≥2 and large n, H_n is the unique 2n-vertex graph with ≥(n²+n)/2 edges forbidding equal-degree endpoints of a 2ℓ-path.

Reference graph

Works this paper leans on

3 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

Bloom, Erd ˝os Problem #816

T. Bloom, Erd ˝os Problem #816. https://www.erdosproblems.com/816
[2]

A problem of Erd\H{o}s and Hajnal on paths with equal-degree endpoints

K. Chen and J. Ma, A problem of Erd ˝os and Hajnal on paths with equal-degree endpoints, arXiv:2503.19569 (2025)

work page Pith review arXiv 2025
[3]

Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications, V ol

P. Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications, V ol. 1 (Kalamazoo, MI, 1988) (1991) 397- –406. Appendix: Proof of Lemma 3.3 Proof of Lemma 3.3. Suppose for a contradiction thatβ≤ ∆− 2 and ∆≥ n + 3. Then there exists a unique vertex v0 in G with d(v0) = ∆. We divide...

work page 1991

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Bloom, Erd ˝os Problem #816

T. Bloom, Erd ˝os Problem #816. https://www.erdosproblems.com/816

[2] [2]

A problem of Erd\H{o}s and Hajnal on paths with equal-degree endpoints

K. Chen and J. Ma, A problem of Erd ˝os and Hajnal on paths with equal-degree endpoints, arXiv:2503.19569 (2025)

work page Pith review arXiv 2025

[3] [3]

Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications, V ol

P. Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications, V ol. 1 (Kalamazoo, MI, 1988) (1991) 397- –406. Appendix: Proof of Lemma 3.3 Proof of Lemma 3.3. Suppose for a contradiction thatβ≤ ∆− 2 and ∆≥ n + 3. Then there exists a unique vertex v0 in G with d(v0) = ∆. We divide...

work page 1991