pith. machine review for the scientific record. sign in

arxiv: 2604.11664 · v1 · submitted 2026-04-13 · 🧮 math.CO

Recognition: unknown

Paths of length five with equal-degree endpoints

Zhen Liu , Qinghou Zeng
Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords extremal graph theorybipartite graphspaths of length fiveequal degreesuniqueness theoremsodd-length pathsChen-Ma conjecture
0
0 comments X

The pith

For all n at least 11, K_{n,n+1} is the unique graph on 2n+1 vertices with at least n squared plus n edges that has no two equal-degree vertices joined by a path of length five.

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

The paper proves an extremal uniqueness result for graphs on an odd number of vertices that avoid a specific configuration: two vertices of the same degree connected by a path of exactly five edges. It shows that once the edge count reaches n squared plus n, the only graph on 2n+1 vertices meeting this threshold without the forbidden configuration is the complete bipartite graph with parts of sizes n and n+1. This extends an earlier theorem that required a much larger n (at least 600) for the shorter path of length three and confirms the next case of a conjecture on odd-length paths with equal-degree endpoints. A reader would care because the result tightens the threshold dramatically and suggests that the same bipartite graph controls the extremal behavior across several odd path lengths.

Core claim

We show that for all n greater than or equal to 11, the complete bipartite graph K_{n,n+1} is the unique graph on 2n+1 vertices with at least n squared plus n edges that contains no two vertices of equal degree joined by a path of length five. This confirms the very next case of the general conjecture of Chen and Ma on paths of odd length with equal-degree endpoints.

What carries the argument

The complete bipartite graph K_{n,n+1} with part sizes n and n+1, which serves as the unique extremal example once the edge count forces the graph to be nearly complete bipartite and the path-length-five condition eliminates all other candidates.

If this is right

  • The uniqueness threshold drops from n at least 600 for length-three paths to n at least 11 for length-five paths.
  • K_{n,n+1} achieves the maximum edge count while satisfying the avoidance condition for this specific forbidden configuration.
  • The general conjecture holds at least for paths of length five on 2n+1 vertices.
  • Similar uniqueness statements are expected to hold for longer odd-length paths under the same edge threshold.

Where Pith is reading between the lines

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

  • The proof likely relies on showing that any graph with the given number of edges must be bipartite and then checking that only the balanced complete bipartite graph survives the degree-path condition.
  • For n between 1 and 10, direct computation could reveal whether smaller graphs obey the same uniqueness or produce counterexamples.
  • If the pattern continues, the same K_{n,n+1} may serve as the unique extremal graph for all odd path lengths greater than or equal to three, with thresholds decreasing as the path length increases.

Load-bearing premise

The edge count of n squared plus n is large enough, for n at least 11, to force any graph on 2n+1 vertices into a structure where the only way to avoid equal-degree endpoints on a five-edge path is to be exactly K_{n,n+1}.

What would settle it

A single graph on 2n+1 vertices, for some n at least 11, that has at least n squared plus n edges, is not isomorphic to K_{n,n+1}, and still contains no two equal-degree vertices at path distance five.

read the original abstract

Addressing a question posed by Erd\H{o}s and Hajnal, Chen and Ma proved that, for all $n \ge 600$, the complete bipartite graph $K_{n,n+1}$ is the unique graph on $2n+1$ vertices with at least $n^2+n$ edges that contains no two vertices of equal degree joined by a path of length three. In this paper, we extend this result and show that, for all $n \ge 11$, $K_{n,n+1}$ is the unique $(2n+1)$-vertex graph with at least $n^2+n$ edges that avoids two equal-degree vertices joined by a path of length five. This confirms the very next case of a general conjecture of Chen and Ma on paths of odd length with equal-degree endpoints.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for all integers n ≥ 11, K_{n,n+1} is the unique graph on 2n+1 vertices with at least n² + n edges containing no two equal-degree vertices joined by a path of length 5. This extends the Chen-Ma theorem (which established the analogous statement for paths of length 3 when n ≥ 600) and confirms the next case of their conjecture on odd-length paths with equal-degree endpoints. The argument proceeds by a stability analysis showing that the edge threshold forces the graph to be bipartite with part sizes n and n+1, followed by a direct verification that only the complete bipartite graph avoids equal-degree vertices at distance 5.

Significance. If the result holds, it constitutes a meaningful advance in the Erdős-Hajnal-type extremal problem on degree-equality along paths. The reduction of the threshold from 600 to 11 via tighter degree-sum and neighborhood-overlap bounds is a concrete technical improvement that renders the statement applicable for small n. The paper supplies a self-contained combinatorial proof that avoids computer assistance, parameter fitting, or self-referential definitions, and it explicitly credits the prior length-three result while deriving the length-five case independently.

minor comments (2)
  1. In the abstract, the phrase 'the very next case of a general conjecture' is clear but would be strengthened by a one-sentence statement of the general form conjectured by Chen and Ma for arbitrary odd lengths.
  2. The stability argument is described at a high level; a brief explicit statement of the key degree-sum inequality used to force bipartiteness (e.g., in the section containing the main proof) would aid readability for readers unfamiliar with the Chen-Ma technique.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript, the accurate summary of our results, and the recommendation to accept. We appreciate the recognition of the technical improvements over the Chen-Ma theorem and the self-contained combinatorial argument.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper extends Chen and Ma's result on P3-avoiding graphs to the P5 case through an independent stability argument: it first shows that any (2n+1)-vertex graph with at least n²+n edges must be bipartite with part sizes n and n+1 (via degree-sum and neighborhood-overlap bounds), then directly verifies that only the complete K_{n,n+1} avoids equal-degree vertices at distance 5. This derivation relies on case analysis and tighter bounds to lower the threshold from 600 to 11, without self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations. The Chen-Ma conjecture supplies context but is not invoked as an unverified premise; the P5 proof stands on its own combinatorial content.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates entirely within standard graph theory; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract statement.

axioms (1)
  • standard math Standard axioms and definitions of graph theory (paths, vertex degrees, bipartite graphs, edge counts).
    The result is stated using classical notions of graphs and paths.

pith-pipeline@v0.9.0 · 5429 in / 1274 out tokens · 66963 ms · 2026-05-10T15:24:03.474752+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

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

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

    math.CO 2026-05 unverdicted novelty 7.0

    For every fixed odd integer k at least 3 and all sufficiently large n, every graph on 2n+1 vertices with n squared plus n plus 1 edges contains two equal-degree vertices joined by a path of length k.

  2. The density of graphs with no $\ell$-path connecting equal-degree vertices: a short proof

    math.CO 2026-05 unverdicted novelty 6.0

    Large graphs with edge density 1/2 + o(1) contain an ℓ-path between two equal-degree vertices, and this density threshold is tight for odd ℓ.

Reference graph

Works this paper leans on

7 extracted references · 1 canonical work pages · cited by 2 Pith papers

  1. [1]

    Bloom, Erd ˝os Problem #816

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

  2. [2]

    Chen and J

    K. Chen and J. Ma, A problem of Erd ˝os and Hajnal on paths with equal-degree endpoints,J. Combin. Theory Ser. B179 (2026) 1–18

    2026

  3. [3]

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

    P. Erd ˝os, Problems and results in combinatorial analysis and combinatorial number theory, In:Graph theory, combinatorics, and applications, V ol. 1 (Kalamazoo, MI, 1988) 397–406 (1991)

    1988

  4. [4]

    Liu and Q

    Z. Liu and Q. Zeng, A complement of the Erd ˝os-Hajnal problem on paths with equal-degree endpoints,arXiv:2505.00523(2025). 5 Appendix: Proof of Theorem 4.1 In this section, we complete the proof of Theorem 4.1. Letn≥13 be an integer and letGbe a graph on 2nvertices with at leastn 2 −1 edges. Assume thatGcontains no two vertices of equal degree joined by ...

    work page arXiv 2025

  5. [5]

    Solving this quadratic inequality in∆yields ∆≤ 6n+5− √ 4n2 −28n−15 4 or∆≥ 6n+5+ √ 4n2 −28n−15 4

    Taking the nearest integer|B|=4n−2∆ +2 gives an upper bound: X v∈V(G) d(v)≤f 2(4n−2∆ +2)=2∆ 2 −(6n+5)∆ +6n 2 +11n+3.(25) 23 From 2e(G)≥2n 2 −2 we obtain 2∆2 −(6n+5)∆ +4n 2 +11n+5≥0. Solving this quadratic inequality in∆yields ∆≤ 6n+5− √ 4n2 −28n−15 4 or∆≥ 6n+5+ √ 4n2 −28n−15 4 . The second lower bound exceeds 2n−1 (impossible), while the first upper bound...

  6. [6]

    Using 2e(G)≥2n 2 −2 we obtain 5 2∆2 − 8n+ 7 2 ∆ +6n 2 +8n+6≥0

    For integerβ, the maximum value is achieved atβ=4n−2∆ +2 or 4n−2∆ +3; substitutingβ=4n−2∆ +2 gives f4(4n−2∆ +2)= 5 2∆2 − 8n+ 7 2 ∆ +8n 2 +8n+4. Using 2e(G)≥2n 2 −2 we obtain 5 2∆2 − 8n+ 7 2 ∆ +6n 2 +8n+6≥0. Solving this quadratic inequality in∆yields either ∆≥ 16n+7+ √ 16n2 −96n−191 10 >2n−1 or∆≤ 16n+7− √ 16n2 −96n−191 10 < 4 3n+ 11 6 . The first is impos...

  7. [7]

    The degree sum must satisfy −2∆2 +(4n+13)∆−14n−11≥2n 2 −2, i.e., −2∆2 +(4n+13)∆−2n 2 −14n−9≥0

    Now substituteβ= ∆−4 into (27): f4(∆−4)=−2∆ 2 +(4n+13)∆−14n−11. The degree sum must satisfy −2∆2 +(4n+13)∆−14n−11≥2n 2 −2, i.e., −2∆2 +(4n+13)∆−2n 2 −14n−9≥0. The discriminant of the left-hand side is (4n+13) 2 −8(2n 2 +14n+9)=97−8n, which is negative forn≥13. This is a contradiction. Combining the above three cases, we conclude that our initial assumptio...