arxiv: 2605.03825 · v1 · submitted 2026-05-05 · 🧮 math.CO

Recognition: unknown

A generalization of ErdH{o}s-Hajnal problem on paths with equal-degree endpoints

Xiamiao Zhao , Yichen Wang , Mei Lu

Authors on Pith no claims yet

Pith reviewed 2026-05-07 15:19 UTC · model grok-4.3

classification 🧮 math.CO

keywords extremal graph theoryErdős-Hajnal conjectureodd pathsequal degreesbipartite graphspath lengthsgraph edges

0 comments

The pith

Every large graph with 2n+1 vertices and n squared plus n plus one edges has two equal-degree vertices joined by an odd-length path.

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

This paper confirms a conjecture extending the Erdős-Hajnal problem from paths of length three to any fixed odd length. It proves that when a graph on 2n+1 vertices has n squared plus n plus one edges, and n is large, it must contain two vertices of the same degree connected by a path of that odd length. The result is interesting because the edge number is tight, as the balanced complete bipartite graph attains it but only allows even-length paths between equal-degree vertices. This shows the forced structure is not limited to short paths.

Core claim

We confirm their conjecture that for every fixed odd integer ℓ ≥ 3 and all sufficiently large n, every (2n+1)-vertex graph with n² + n + 1 edges contains two vertices of equal degree that are connected by a path of length ℓ.

What carries the argument

The complete bipartite graph K_{n,n+1} serves as the extremal example achieving the maximum edges without creating an odd-length path between equal-degree vertices, and the argument shows that any graph with this many edges must deviate in a way that creates such a path.

If this is right

The conjecture holds for every odd length ℓ at least 3 when n is large.
The same edge bound suffices for longer paths as for length 3.
Graphs exceeding this edge count are guaranteed the property for all large n.
Only the bipartite construction avoids the conclusion for each fixed odd ℓ.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The proof technique might extend to even path lengths with a different edge threshold.
Similar forcing results could apply to other distance conditions or to multiple paths.
Small values of n could be checked separately to determine the exact threshold for each ℓ.
This generalizes the understanding of how edge density controls degree and connectivity properties in graphs.

Load-bearing premise

The statement requires n to be large enough for the proof's asymptotic techniques to guarantee the existence of the path.

What would settle it

A specific counterexample for a large n would be a (2n+1)-vertex graph with exactly n² + n + 1 edges that has no path of length ℓ connecting any two vertices of equal degree.

Figures

Figures reproduced from arXiv: 2605.03825 by Mei Lu, Xiamiao Zhao, Yichen Wang.

**Figure 1.** Figure 1: An illustration of the sets Y12, Y1 and Y2. Note that γ ≤ d = b12 − 2c − 1 and b12 ≤ β − α = n + c. Then we have that |M[B12, D]| ≥ b12d − (d + (d − 1) + . . . + (d − (d − γ + 1)) + γ + . . . + γ) = b12d − (d + γ + 1)(d − γ) 2 − γ(b12 − (d − γ)) = b12 + 1 2 − γ 2 − 2c 2 − c − (2c + 1)γ − b12 ≥ b12 + 1 2 − γ 2 + 2c 2 + 3c + 1 − 2(c + 1)b12 ≥ b12 + 1 2 − γ 2 − 2nc − 2n. (6) Similarly … view at source ↗

**Figure 2.** Figure 2: An illustration of the path u1v1t1w1w2t2w3 . . . wℓ−1tℓ−1v2u2. If y12 < γ − Cn0.5 , then clearly γ ≥ Cn0.5 , and we can get a refined bound for |M[Y ]| from (7). That is |M[Y ]| ≥γ 2 − (γ − Cn0.5 ) 2 2 − γ − Cn0.5 2 − 8ℓn ≥ γ 2 + C 2 2 n − 8ℓn. (9) Then combining (5), (6) and (9), we have that |M| ≥ c 2 + n 2 − 33ℓn + C 2 2 n. (10) Since C is a large constant, we have a contradiction with (1). Now we f… view at source ↗

**Figure 4.** Figure 4: The case when G[D′ ] is not empty with an edge w1w2 view at source ↗

**Figure 5.** Figure 5: The case when G[D1] is not empty view at source ↗

**Figure 7.** Figure 7: An illustration of the vertex u and the sets S1, S2, A, B, C, Z. Proof. Suppose ∆ < n + √ n. By the definition of β, we have that S ≤ ∆ + (∆ − 1) + . . . + β + β + . . . + β ≤ (∆ + β)(∆ − β + 1) 2 + β(2n + 1 − (∆ − β + 1)) ≤ (∆ + n)(∆ − n + 1) 2 + n(3n − ∆) ≤ (2n + √ n)(√ n + 1) 2 + n(2n − √ n) ≤ 2n 2 + 3 2 n + 1 2 √ n < 2n 2 + 2n, when n is large enough, a contradiction with (2). □ Let u ∈ V (G) with d(u)… view at source ↗

read the original abstract

Erd\H{o}s and Hajnal proposed a problem that: is it true that every $(2n+1)$-vertex graph with $n^2+n+1$ edges contains two vertices of equal degree connected by a path of length three? The edge bound is sharp by the complete bipartite graph $K_{n,n+1}$. Recently, Chen and Ma [Journal of Combinatorial Theory, Series B, 179:1-18, 2026] answered this problem affirmatively for every $n \ge 600$. In the same paper, they further conjectured that for sufficiently large $n$, the statement is true if we replace the path of length three by a path of fixed odd length. In this paper, we confirm their conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the Chen-Ma conjecture for arbitrary fixed odd path lengths via a stability argument on near-bipartite graphs.

read the letter

The core result is that for any fixed odd ℓ at least 3, every graph on 2n+1 vertices with n² + n + 1 edges has two equal-degree vertices joined by a path of length ℓ, once n exceeds some threshold depending on ℓ. This directly confirms the conjecture and extends the length-3 case that Chen and Ma handled for n at least 600. The edge bound stays sharp by the same K_{n,n+1} example. They achieve this with a stability method: first show that any such graph is close in edit distance to the complete bipartite graph K_{n,n+1} or its complement, then use the resulting degree sequence to count odd-length path extensions between equal-degree vertices. The counting stays elementary and deterministic, with no regularity lemmas or probabilistic error terms. The dependence of the stability threshold on ℓ is made explicit, which is useful. One soft spot is that the n threshold grows with ℓ, so the result is genuinely asymptotic and leaves small-n cases open, though the conjecture only claims the large-n regime. No circular reasoning appears, and the argument does not rely on unverified external results. This work is for people already following extremal problems on degrees and paths. It deserves peer review because it resolves a stated conjecture with a self-contained combinatorial proof that can be checked directly.

Referee Report

0 major / 3 minor

Summary. The manuscript confirms the conjecture of Chen and Ma by proving that, for every fixed odd integer ℓ ≥ 3 and all sufficiently large n, every graph on 2n+1 vertices with exactly n² + n + 1 edges contains two vertices of equal degree joined by a path of length ℓ. The proof proceeds via a stability argument establishing that any such graph is close to the complete bipartite graph K_{n,n+1} (or its complement), followed by a deterministic counting argument on degree sequences that guarantees the existence of an odd-length path between equal-degree vertices.

Significance. If the proof holds, the result fully resolves the stated conjecture in extremal graph theory, extending the original Erdős-Hajnal question from paths of length 3 to arbitrary fixed odd lengths. The stability-based approach is a strength: it is purely combinatorial, avoids regularity lemmas or probabilistic methods with uncontrolled errors, and makes the dependence on n (growing with ℓ but finite for each fixed ℓ) explicit. This provides a clean, deterministic confirmation that is sharp by the extremal example K_{n,n+1}.

minor comments (3)

In the statement of the main theorem (likely Theorem 1.1 or 1.2), the phrase 'sufficiently large n' is used without an explicit quantitative bound; while an existence proof does not require the bound, adding a remark on how the stability threshold depends on ℓ would improve readability.
Section 2 (preliminaries or stability lemma): the error term in the edge-distance to K_{n,n+1} is described as o(n²); a brief explicit inequality (e.g., at most ε n² edges away for n > N(ℓ,ε)) would make the subsequent path-counting inequalities easier to verify.
The citation to Chen and Ma (Journal of Combinatorial Theory, Series B, 179:1-18, 2026) appears in the introduction; ensure the full bibliographic details, including the exact title of their paper, are included in the references section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The referee's summary accurately reflects both the statement of the result and the stability-based proof strategy we employ.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript states and proves the Chen-Ma conjecture via an explicit stability argument: any (2n+1)-vertex graph with n²+n+1 edges is shown to be close to K_{n,n+1} (or its complement), after which a direct, deterministic counting argument on degree sequences and odd-length path extensions yields the equal-degree pair for fixed odd ℓ and all sufficiently large n. No step reduces to a fitted parameter, self-definition, or load-bearing self-citation; the sole citation to Chen-Ma is used only to identify the statement being proved. The derivation is therefore self-contained and independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard axioms of graph theory and extremal combinatorics with no free parameters or invented entities mentioned in the abstract.

axioms (1)

standard math Graphs are finite, simple, undirected, and without multiple edges or loops.
Implicit background assumption for all statements about vertex degrees and paths in the abstract.

pith-pipeline@v0.9.0 · 5431 in / 1148 out tokens · 76550 ms · 2026-05-07T15:19:13.779787+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

5 extracted references · 2 canonical work pages · 1 internal anchor

[1]

Chen and J

K. Chen and J. Ma. A problem of Erdős and Hajnal on paths with equal-degree endpoints. Journal of Combinatorial Theory, Series B, 179:1–18, 2026

2026
[2]

P. Erdős. Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, 1:397–406, 1991. 16

1991
[3]

Erdős and T

P. Erdős and T. Gallai. On maximal paths and circuits of graphs.Acta Math. Acad. Sci. Hungar., 10(3):337–356, 1959

1959
[4]

Liu and Q

Z. Liu and Q. Zeng. A complement of the Erdős-Hajnal problem on paths with equal-degree endpoints.arXiv e-prints, arXiv:2505.00523, May 2025

work page arXiv 2025
[5]

Paths of length five with equal-degree endpoints

Z. Liu and Q. Zeng. Paths of length five with equal-degree endpoints.arXiv e-prints, arXiv:2604.11664, 2026. 17

work page internal anchor Pith review Pith/arXiv arXiv 2026