Erdos-Gallai Stability Theorem for Linear Forests

Ming-Zhu Chen; Xiao-Dong Zhang

REVIEW 2 major objections 5 minor 12 references

Erdos-Gallai Stability Theorem for Linear Forests

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A minimum-degree threshold forces every linear forest into a large connected graph unless the graph belongs to a short list of explicit exceptions.

desk verdict The results are a genuine extension in minimum-degree stability for linear forests, but the proof as posted is unsound at Lemma 2.4(iii), so it needs major revision before I would rely on it. read the letter →

arxiv 1908.00665 v1 pith:23XYCYUL submitted 2019-08-02 math.CO

Ming-Zhu Chen , Xiao-Dong Zhang This is my paper · ORCID

classification math.CO MSC 05C3505C3805C05

keywords Erdős-Gallaitheoremstabilityversionminimumdegreelinearforestpathembeddingextremalgraphtheory2-connectedgraphscutvertex

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

This paper proves a stability version of the Erdős-Gallai theorem for linear forests. For a connected graph on sufficiently many vertices with minimum degree at least h—the sum of half-lengths of the forest's paths minus one—every linear forest made of even paths and at most two odd paths must appear as a subgraph, unless the graph is one of a short list of explicitly described exceptional families. The result subsumes the earlier even-path and odd-path stability theorems and shows that the degree condition is best possible. Its significance is that it identifies exactly which graphs resist the embedding, not merely an extremal edge count.

What carries the argument

The central object is the parameter $h=\sum_i a_i+\sum_i b_i-1$, which is half the total number of vertices of $F$ minus one. The proof mechanism is a longest-cycle analysis: Lemma 2.2 forces a cycle of length at least $2h$ in a 2-connected graph with $\delta(G)\ge h$, while the forbidden path $P_{2h+4}$ bounds the cycle length above. Lemma 2.4(iii) then asserts that when the longest cycle has length $2h+2$ and $P_{2h+4}$ is absent, all vertices outside the cycle have the same neighborhood on the cycle, of size $h$ or $h+1$. Lemma 4.2 uses this to reduce the cycle length to $2h$ or $2h+1$, and Corollaries 4.4–4.7 classify the residual structure into the exceptional families; in the cut-vertex case the same parameter controls end-block sizes, producing the clique-necklace graphs.

What would settle it

Search for a connected graph $G$ with $\delta(G)\ge 3$, longest cycle $C_8$, no path $P_{10}$, and two vertices outside $C_8$ whose neighborhoods on $C_8$ differ; if such a graph exists, Lemma 2.4(iii) fails and the exception list must be enlarged. The proof of Lemma 2.4(iii) in Section 2 asserts the identical-neighborhood conclusion rather than deriving it, so an explicit example or contradiction at this point settles the hinge.

Watch

Extended reading notes

Core claim

Theorems 1.8–1.11 assert the following. Let $F=(\bigcup_{i=1}^k P_{2a_i})\cup(\bigcup_{i=1}^2 P_{2b_i+1})$ be a linear forest with $k\ge 0$ and at most two odd paths, and set $h=\sum_i a_i+\sum_i b_i-1$. If $G$ is connected (or 2-connected) of sufficiently large order $n$ and $\delta(G)\ge h$, then $F\subseteq G$ unless $G$ is one of the listed exceptions: $S_{n,h}=K_h\vee \overline{K}_{n-h}$, $S^+_{n,h}=K_h\vee(K_2\cup \overline{K}_{n-h-2})$, $L_{t,h}=K_1\vee tK_h$, the parity-sensitive joins $K_2\vee \frac{n-2}{2}K_2$ and $K_3\vee \frac{n-3}{2}K_2$ in specific cases, or the cut-vertex families $H^1_n$, $H^2_n$, $U_{3,h}$, $L_{t_1,t_2,h,h+1}$, $F_{t_1,t_2,h,h+1}$, and $T_{t_1,t_2,h,h+1}$. The paper also constructs examples showing that lowering the minimum degree to $h-1$ admits infinitely many $F$-free graphs outside every listed exception, so the bound $h$ is tight.

Load-bearing premise

The classification hinges on Lemma 2.4(iii): when the longest cycle has length $2h+2$ and $P_{2h+4}$ is absent, every vertex outside the cycle must have the same neighbors on the cycle, and that common neighborhood has size $h$ or $h+1$; this is stated without a full derivation and the 2-connected theorems collapse if it is false.

Editorial extensions

If this is right

The minimum-degree condition $\delta(G)\ge h$ is sharp for every family considered: dropping to $h-1$ creates infinitely many $F$-free graphs outside all listed exceptions, as shown by the $L_{(n-1)/(h-1),h-1}$ examples in Remarks 1 and 2.
For a pure even forest ($l=0$), only two exceptions occur, $S_{n,h}$ and $L_{t,h}$, so the stability description is nearly trivial.
For a forest with one odd path, the exceptions add the parity-sensitive join $K_2\vee \frac{n-2}{2}K_2$ and the $L_{t,h}$ case with two special path-length pairs.
For two odd paths and no even path, the cut-vertex theorem produces a finite catalogue $U_{3,h}$, $L_{t_1,t_2,h,h+1}$, $F_{t_1,t_2,h,h+1}$, $T_{t_1,t_2,h,h+1}$, plus $H^1_n$ and $H^2_n$ in the small case.
The combined result strengthens the edge-count extremal theorem for linear forests to a minimum-degree stability statement, with the same main exceptions reappearing in the 2-connected case.

Reading between the lines

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

Not asserted in the paper: the same mechanism should extend to forests with more than two odd paths, with an exception list built from larger joins of cliques, keeping $h$ as half the total length minus one.
Not asserted in the paper: the longest-cycle classification suggests an analogous stability theorem for disjoint unions of cycles, with the threshold equal to the sum of cycle half-lengths minus one.
Not asserted in the paper: the exceptional families in the 2-connected theorems depend on the parity of $n$, so an explicit parity-dependent version for every $n$, rather than only sufficiently large $n$, is plausible.
Not asserted in the paper: if Lemma 2.4(iii) fails for some $h$, the likely fix is a single added exception family where outside vertices split between two alternating neighborhoods on the long cycle.

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 new content is real. Theorems 1.8–1.11 are the first minimum-degree stability statements for linear forests with several path components and at most two odd paths; they do not reduce to the earlier Ali–Staton and Yuan–Nikiforov single-path theorems, and the listed exceptional families look plausible. The broad strategy—longest cycles for the 2-connected case, end-block arguments for the cut-vertex case—is the right toolkit, and the citations to prior work are appropriate. If the proof can be repaired, this is a solid subfield result.

But the paper is not acceptable as posted, because Lemma 2.4(iii) is false. The stress-test counterexample works. For h=3, take an 8-cycle v1...v8, add two independent vertices x,y with N(x)={v2,v4,v6} and N(y)={v2,v4,v8}, and add chords v1v4, v3v6, v5v8, v7v2. The graph is bipartite with parts {v1,v3,v5,v7,x,y} and {v2,v4,v6,v8}; hence no cycle has length more than 8 and no path has 10 vertices. Vertices all have degree at least 3, so delta(G)=3, the longest cycle has length 8, and U={x,y} is independent. But N_{C8}(x) differs from N_{C8}(y), contradicting Lemma 2.4(iii). The proof's step “N_C(u1) lies in a path of 2h-1 consecutive vertices, hence d_C(u1)≤h-1” is simply wrong: a path on 2h-1 vertices has independence number h, not h-1. Since Lemma 4.2 uses Lemma 2.4(iii) to rule out l=2h+2, the proof of Theorem 1.10 is unsound at a load-bearing point. The counterexample still contains the relevant h=3 forests, so the theorem statements may survive, but this text does not prove them.

There are smaller issues consistent with the same pattern. Lemma 4.10 is stated for b1,b2≥3, yet its h=2 branch treats P2∪2P3, which has b1=b2=1; it also cites Lemma 4.1(ii) when Lemma 4.1(iii) is the statement about P2∪2P3. Theorem 1.11(b) then invokes Lemma 4.10 for b2=1,2, outside the stated range. These may be fixable in a careful rewrite, but they are not merely typographical because the proof logic jumps through the wrong range.

The paper is for extremal graph theorists working on degenerate Turán and stability problems. I would send it to a serious referee rather than desk-reject, because the main claims are important, plausible, and genuinely extend known results. But my expectation would be major revision, and the referee should be asked to verify every lemma rather than the theorem statements alone. I would not cite the current arXiv version.

Referee Report

2 major / 5 minor

Summary. The paper proves stability versions of the Erdős–Gallai theorem for linear forests consisting of an arbitrary number of even paths together with at most two odd paths. For a connected or 2-connected graph G of sufficiently large order n with minimum degree at least h = (sum of half path lengths) - 1, the authors claim that F embeds in G unless G belongs to one of several explicitly listed exceptional families, including S_{n,h}, S^+_{n,h}, L_{t,h}, joins of K_2 or K_3 with a matching, H^1_n, H^2_n, U_{3,h}, F_{t1,t2,h,h+1}, and T_{t1,t2,h,h+1}. The proofs use longest cycles, block decompositions, and a common-neighborhood lemma of Lidický–Liu–Palmer, and the paper includes sharpness examples for the minimum degree condition.

Significance. If the main theorems are correct, they unify and extend prior results of Ali–Staton for even paths and Yuan–Nikiforov for odd paths to linear forests with up to two odd components, and they provide a fairly complete stability classification. The paper is commendably explicit about the exceptional families and includes minimum-degree sharpness constructions. The stability argument is self-contained apart from standard external tools, and the statements are precise and falsifiable. However, the proof currently rests on a stated lemma that is false, so the significance is contingent on repairing that part of the argument.

major comments (2)

[Section 2, Lemma 2.4(iii)] Lemma 2.4(iii) is false as stated. For h=3, take a cycle C8 on v1,...,v8, add independent vertices x,y with N(x)={v2,v4,v6} and N(y)={v2,v4,v8}, and add the chords v1v4, v3v6, v5v8, v7v2. The resulting graph is bipartite with parts {v1,v3,v5,v7,x,y} and {v2,v4,v6,v8}, so every cycle has length at most 8 and every path has at most 9 vertices; in particular P10 is absent. Each vertex has degree at least 3, U={x,y} is independent, and N_C(x) differs from N_C(y), so the hypotheses of Lemma 2.4(iii) hold while the conclusion fails. The proof's step claiming that N_C(u1) lies in a path of 2h-1 consecutive vertices and hence d_C(u1) ≤ h-1 is invalid: that path has independence number h, not h-1. This lemma is load-bearing: Lemma 4.2 uses it to rule out l=2h+2, and Lemma 4.1(ii) Case 4 uses it for the l=6 case; consequently the proofs of Theorems 1.10 and parts of Lemma 4.1 are unsound as written.
[Section 4, Lemma 4.10 and Theorem 4.11(b)] Lemma 4.10 is stated only for b1,b2 ≥ 3, but Theorem 4.11(b) requires the conclusion for all b1 ≥ b2 ≥ 1. The proof of Theorem 4.11(b) simply invokes Lemma 4.10, so the cases b2=1 and b2=2 are not covered. Moreover, the h=2 branch inside Lemma 4.10's proof is inconsistent with the lemma's own assumptions: if b1,b2 ≥ 3 and k ≥ 1, then h ≥ 1+3+3-1 = 6, so h=2 cannot occur. That branch also cites Lemma 4.1(ii), which concerns P5 ∪ P3, whereas the case F = P2 ∪ 2P3 needs Lemma 4.1(iii). Thus Theorem 4.11(b) is not proved for the small odd-path cases it claims to cover.

minor comments (5)

[Abstract and Introduction] The abstract contains a grammatical error: 'extends and strengths' should be 'extends and strengthens'.
[Theorem 4.11 proof] In the proof of Theorem 4.11(a), the citations to 'Lemma 4.6 (i)' and 'Lemma 4.6 (ii)' should be to Lemma 4.1(i) and Lemma 4.1(ii), respectively; there is no Lemma 4.6 with parts (i) and (ii) in the stated form.
[Lemma 2.7(iii) proof] In the proof of Lemma 2.7(iii), the notation NP6(v) is written inconsistently as {v2,v4}, {v2,v5}, {u2}, {u4}, {u5}; the path vertices are denoted u1,...,u6, so these should all use the u notation.
[Lemma 4.9 proof] The first sentence of the proof of Lemma 4.9 contains a leftover summation index: since k=0 in that lemma, the displayed sum should be Σ_{i=1}^2 (2b_i+1) = 2h+4 rather than Σ_{i=1}^k 2a_i + Σ_{i=1}^2 (2b_i+1).
[Theorem 1.11(b)] The statement of Theorem 1.11(b) has a typo: 'δ(G) ≥ h ≥ 2 an k ≥ 1' should read 'δ(G) ≥ h ≥ 2 and k ≥ 1'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all load-bearing lemmas are prior external results or direct case arguments; the sole flagged issue is a proof gap in Lemma 2.4(iii), not a circular reduction.

full rationale

The derivation is self-contained against external benchmarks. Theorems 1.8–1.11 are proved from classical external black boxes (Erdős–Gallai [6] as Lemma 2.1, Dirac [5] as Lemma 2.2, and Lidický–Liu–Palmer [8] as Lemma 2.3) plus new case analyses; no parameter is fitted to data and no target statement is assumed in a lemma. The self-citations [4] and [11] appear only as background references and are not load-bearing. The only questionable step is Lemma 2.4(iii), whose proof that P_{2h+4}-freeness forces N_C(u1) to lie in 2h−1 consecutive cycle vertices, then jumps from 'no two consecutive neighbors on the cycle' to d_C(u1) ≤ h−1; since a no-two-consecutive subset of 2h−1 vertices can have h elements, the intended bound is not derived. This makes Lemma 4.2's use of Lemma 2.4(iii) a soundness risk, but it is not a circularity: it does not redefine an input as an output, fit a parameter, or rely on the authors' prior claims. Accordingly the circularity score is 0.

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

No free parameters or invented entities. The paper is a pure extremal graph theory proof. It relies on standard prior theorems as black boxes and proves its own structural lemmas; the main risk is the correctness and scope of those internal lemmas, not circularity.

assumptions (3)

standard math Erdős-Gallai Lemma 2.1: a 2-connected graph with all vertices except possibly u1 of degree at least h contains a path of order min{n,2h} with end vertex u1.
Used repeatedly to force long paths from end blocks and cycles; accepted external theorem, not fitted.
standard math Dirac's theorem Lemma 2.2: a 2-connected graph with minimum degree at least h contains a cycle of length at least 2h.
Provides the starting longest cycle for the stability analysis.
standard math Lidický-Liu-Palmer Lemma 2.3: for large n, large bipartite edge density between a small set and its complement forces a large common neighborhood.
Used in Lemma 4.6 to find a complete bipartite structure in the 2-connected case; an external theorem with an explicit n threshold.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Erdos-Gallai Stability Theorem for Linear Forests." pith.science (2026). https://pith.science/paper/23XYCYUL

@misc{pith2026190800665,
  author       = {Pith},
  title        = {Pith review of: Erdos-Gallai Stability Theorem for Linear Forests},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/23XYCYUL}},
  note         = {Machine review of arXiv:1908.00665}
}

abstract

The Erd\H{o}s-Gallai Theorem states that every graph of average degree more than $l-2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erd\H{o}s-Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=(\bigcup_{i=1}^kP_{2a_i})\bigcup(\bigcup_{i=1}^lP_{2b_i+1})$ be $k+l$ disjoint paths of order $2a_1, \ldots, 2a_{k}, 2b_1+1, \ldots, 2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\geq 2$. If the minimum degree $\delta(G)\ge \sum_{i=1}^ka_i+\sum_{i=1}^lb_i-1$, then $F\subseteq G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.

Figures

Figures reproduced from arXiv: 1908.00665 by the authors.

**Figure 2.** Fig.2. Graphs [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Fig.3. Graphs [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Fig.4 [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat

B. Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat. Lapok 13 (1962) 95-107

work page 1962
[2]

Ali and W

A.A. Ali and W. Staton, On extremal graphs with no long paths, Electron. J. Combin. 3 (1996), Research Paper 20, approx. 4 pp

work page 1996
[3]

Bushaw and N

N. Bushaw and N. Kettle, Tur\' a n numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837--853

work page 2011
[4]

Chen and X.-D

M.-Z. Chen and X.-D. Zhang, The number of edges, spectral radius and Hamilton-connectedness of graphs, J. Comb. Optim. 35 (2018) 1104--1127

work page 2018
[5]

Dirac, Some theorems on abstract graphs, Proc

G.A. Dirac, Some theorems on abstract graphs, Proc. London Math Soc. 2 (1952) 69--81

work page 1952
[6]

Erd o s and T

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

work page 1959
[7]

u redi, A. Kostochka, J. Verstra\

Z. F\" u redi, A. Kostochka, J. Verstra\" e te, Stability in the Erd o s--Gallai Theorems on cycles and paths, J. Combin. Theory Ser. B, 121 (2016) 197-228

work page 2016
[8]

Gorgol, Tur\' a n number for disjoint copies of graphs, Graphs Combin

I. Gorgol, Tur\' a n number for disjoint copies of graphs, Graphs Combin. 27 (2011) 661-667

work page 2011

Show all 12 references

[9]

Lidick\' y , H

B. Lidick\' y , H. Liu, C. Palmer, On the Tur\' a n number of forests, Electron. J. Combin. 20 (2) (2013) Paper 62, 13 pp

2013
[10]

Nikiforov and X.Y

V. Nikiforov and X.Y. Yuan, Maxima of the Q -index: graphs without long paths, Electron. J. Linear Algebra 27 (2014) 504--514

2014
[11]

West, Introduction to Graph Theory, Prentice-Hall, London, 2001

D.B. West, Introduction to Graph Theory, Prentice-Hall, London, 2001

2001
[12]

Yuan and X.-D Zhang, The Tur\' a n number of disjoint copies of path, Discrete Math

L.-T. Yuan and X.-D Zhang, The Tur\' a n number of disjoint copies of path, Discrete Math. 340 (2) (2017) 132-139

2017

Pith tools

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

[1] [1]

Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat

B. Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat. Lapok 13 (1962) 95-107

work page 1962

[2] [2]

Ali and W

A.A. Ali and W. Staton, On extremal graphs with no long paths, Electron. J. Combin. 3 (1996), Research Paper 20, approx. 4 pp

work page 1996

[3] [3]

Bushaw and N

N. Bushaw and N. Kettle, Tur\' a n numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837--853

work page 2011

[4] [4]

Chen and X.-D

M.-Z. Chen and X.-D. Zhang, The number of edges, spectral radius and Hamilton-connectedness of graphs, J. Comb. Optim. 35 (2018) 1104--1127

work page 2018

[5] [5]

Dirac, Some theorems on abstract graphs, Proc

G.A. Dirac, Some theorems on abstract graphs, Proc. London Math Soc. 2 (1952) 69--81

work page 1952

[6] [6]

Erd o s and T

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

work page 1959

[7] [7]

u redi, A. Kostochka, J. Verstra\

Z. F\" u redi, A. Kostochka, J. Verstra\" e te, Stability in the Erd o s--Gallai Theorems on cycles and paths, J. Combin. Theory Ser. B, 121 (2016) 197-228

work page 2016

[8] [8]

Gorgol, Tur\' a n number for disjoint copies of graphs, Graphs Combin

I. Gorgol, Tur\' a n number for disjoint copies of graphs, Graphs Combin. 27 (2011) 661-667

work page 2011