{"id":"a3ac0138-fa95-49ba-9032-d8ffdb1fc476","arxiv_id":"2505.00523","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every n at least 2, every (2n+1)-vertex graph with at least n^2+n+1 edges contains two equal-degree vertices joined by a path of length three, with K_{n,n+1} as the unique extremal graph.","lead":"This paper resolves a 1991 question by Erdos and Hajnal for every n at least 2: any graph with 2n+1 vertices and at least n^2+n+1 edges must contain two equal-degree vertices joined by a path of length three. The only extremal graph without such a path is the complete bipartite graph K_{n,n+1}.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved n=3 equality case in Lemma 3.2 leaves Theorem 1.5 unverified at its base case.","rationale":"The central claim of the paper is that Theorem 1.5 holds for all n≥3. The weakest point in the proof is the n=3 base case inside Lemma 3.2, where the authors invoke an unproved 'characterization' of the tight degree-sum equality. This is genuinely load-bearing because no other lemma covers n=3. However, the reader's identified mechanism for this failure — the path w1z1z2w2 requiring adjacency that may not hold — is not actually the problem, since in the even case z1 is universal and z2 has at most one non-neighbor; one of the two paths always forms. The real gap is the unproved equality-case analysis, which is finite and can be settled by exhaustive search or a short analytic argument. The rest of the proof, including the lengthy Lemma 3.3, appears recoverable despite pervasive notation and cross-reference typos. Therefore the conditional verdict is appropriate, and the paper should be accepted once the n=3 equality case is written out or machine-checked.","tokens_in":13521,"tokens_out":44669,"duration_ms":395911,"concrete_test":"Run a brute-force enumeration of all graphs on 6 labeled vertices (or all graphs with degree sequence (5,3,2,2,2,2), which is the only equality case in the n=3 bound) and test whether any graph with β≤2 and at least 8 edges avoids a path of length 3 between equal-degree vertices. If none exists, the missing 'characterization' in Lemma 3.2 is confirmed; if one exists, Theorem 1.5 is false for n=3. This finite check settles the concern directly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 3.2 (Section 3), the proof of β≥3 for the even case has an unproved corner case. When β≤2, the degree-sum bound 2e(G)≤2n^2−3n+7 is tight exactly when n=3, and the proof says only 'At this time, the graph G can be characterized and there exists a path of length three with equal-degree endpoints' without giving the characterization. Since Lemma 3.3 covers n≥6 and Lemma 3.4 covers n=4,5, this unproved assertion is the sole support for Theorem 1.5 at n=3. The reader's specific concern about the path w1z1z2w2 failing when z1 or z2 is non-adjacent to w1 is actually not the obstruction: in the even case z1 has degree 2n−1 and is universal, and z2 has degree 2n−2 with at most one non-neighbor, so one of the two displayed paths always exists. The real missing piece is the n=3 tight case, which is finite and easy to verify but is not supplied in the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13752,"tokens_out":64698,"duration_ms":497421,"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":[{"comment":"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.","section":"§3, Lemma 3.2"},{"comment":"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.","section":"§2, Lemma 2.6 and §3, Lemma 3.4"}],"minor_comments":[{"comment":"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.","section":"§3, proof of Theorem 1.5, Case 1"},{"comment":"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.","section":"§3, Lemma 3.4"},{"comment":"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...'.","section":"§3, proof of Theorem 1.5, Case 2"},{"comment":"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.","section":"§3, Cases 1–3"},{"comment":"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'.","section":"§2, Lemma 2.6; §3, Lemma 3.4"},{"comment":"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.","section":"Appendix, proof of Lemma 3.3"},{"comment":"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.","section":"§2, Lemmas 2.3 and 2.5"}],"recommendation":"major_revision","confidential_remarks":"The odd-vertex theorem (Theorem 1.3) is the main result and appears correct; the even-vertex theorem (Theorem 1.5) has a genuine but small gap at n=3 and would be fully established by supplying the finite verification described in Major Comment 1. The manuscript also contains two false lemma statements and numerous citation and typographical errors, which suggests the final version needs a careful proofreading pass. The reliance on the concurrent Chen–Ma preprint for Lemmas 2.3 and 2.5 should be handled transparently in the published version. I would encourage the editor to send the paper back for revision rather than reject it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOverall 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.\n\nWho 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.","headline":"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.","tokens_in":14222,"tokens_out":1139,"would_cite":true,"duration_ms":12750,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C07"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["equal-degree vertices","path of length three","Erdős-Hajnal problem","extremal graph","complete bipartite graph","degree sequence","complement counting","sharp edge bound"],"falsifier":"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.","tokens_in":13351,"feed_emoji":"🔗","tokens_out":14207,"duration_ms":143029,"temperature":0.7,"pith_summary":"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$.","feed_headline":"n≥2: one extra edge creates an equal-degree path of length 3","feed_subtitle":"K_{n,n+1} is the unique extremal graph, closing the Erdős–Hajnal problem for all n.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Identifies the question as Erdős Problem #816, the statement the paper resolves.","marker":"[1]"},{"why":"Supplies the earlier $n\\ge600$ odd-order theorem, the even-order analogue for large $n$, and the degree-dichotomy and degree-distinctness lemmas reused here.","marker":"[2]"},{"why":"States the original 1991 Erdős–Hajnal problem that the paper answers completely.","marker":"[3]"}],"fun_headline_variants":["One extra edge over K_{n,n+1} forces equal-degree path of length 3","Erdős–Hajnal path problem fully resolved for all n≥2","Sharp threshold: >n^2+n edges guarantee equal-degree path in (2n+1)-vertex graphs","K_{n,n+1}: unique extremal graph in equal-degree path theorem for all n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One extra edge over K_{n,n+1} forces equal-degree path of length 3","Erdős–Hajnal path problem fully resolved for all n≥2","Sharp threshold: >n^2+n edges guarantee equal-degree path in (2n+1)-vertex graphs","K_{n,n+1}: unique extremal graph in equal-degree path theorem for all n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002036,"raw_usage":{"total_tokens":7878,"prompt_tokens":837,"completion_tokens":7041,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":453,"completion_tokens_details":{"reasoning_tokens":6942}},"tokens_in":453,"tokens_out":7041,"duration_ms":52178,"temperature":1.0,"reasoning_tokens":6942,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:44:26.630913+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A problem of Erd\\H{o}s and Hajnal on paths with equal-degree endpoints","cited_arxiv_id":"2503.19569","evidence_quote":"Supplies the earlier $n\\ge600$ odd-order theorem, the even-order analogue for large $n$, and the degree-dichotomy and degree-distinctness lemmas reused here."},{"cited_title":"Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications, V ol","cited_arxiv_id":null,"evidence_quote":"States the original 1991 Erdős–Hajnal problem that the paper answers completely."}],"review_version":1}