{"id":"7813e853-ce0d-494e-b85c-d5304d73d59c","arxiv_id":"1908.00665","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For sufficiently large connected graphs, minimum degree at least h forces any fixed linear forest with at most two odd paths, except for explicit families of graphs.","lead":"This mathematics paper proves stability versions of the Erdős-Gallai theorem: it lists the exact exceptional graphs that keep a large, connected graph with high minimum degree from containing a prescribed disjoint union of paths. The result extends known stability theorems for one path to forests made of several paths with up to two odd components.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.4(iii) is false as stated: an explicit h=3 graph with δ=3, longest cycle 8, and no P10 has two outside vertices with different cycle-neighborhoods; Lemma 4.2's proof is therefore unsound.","rationale":"The reader's weakest assumption identified Lemma 2.4(iii) as the hinge, and this is exactly where the proof collapses. I found an explicit graph satisfying the lemma's hypotheses for h=3 whose outside vertices have different cycle-neighborhoods, so the lemma is false as stated. The error is a concrete miscomputation of the independence number of a path of 2h-1 vertices. Because Lemma 4.2 depends on this lemma, the proof of the 2-connected classification in Theorem 1.10 cannot be accepted as written. At the same time, the counterexample embeds the relevant target forests, so it does not constitute a counterexample to the central theorem. The other issues noted by the reader, such as the parameter-range mismatch in Lemma 4.10 and the wrong citation in Theorem 4.11(b), are real but secondary. Since no counterexample to the main theorems was found, the conditional verdict remains appropriate; the authors need to repair or replace Lemma 2.4(iii) and the dependent arguments.","tokens_in":25591,"tokens_out":46897,"duration_ms":451218,"concrete_test":"Check the following 10-vertex graph: C8=v1...v8v1, plus vertices x,y with N(x)={v2,v4,v6}, N(y)={v2,v4,v8}, plus chords v1v4, v3v6, v5v8, v7v2. Verify that it is bipartite with parts {v1,v3,v5,v7,x,y} and {v2,v4,v6,v8}, that δ=3, that the longest cycle has length 8, that P10 is absent, and that U={x,y} is independent with N_C(x)≠N_C(y). Confirming these facts refutes Lemma 2.4(iii), so Lemma 4.2's citation of it is invalid and the proof of Theorem 1.10 must be repaired.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 2.4(iii) is not merely underived; it is false. Counterexample for h=3: start with C8 on v1,...,v8, add 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 A={v1,v3,v5,v7,x,y} and B={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). Thus the hypotheses of Lemma 2.4(iii) hold for h=3 and the conclusion fails. The proof's step 'N_C(u1) lies in a path of 2h-1 consecutive vertices, hence d_C(u1)≤h-1' is invalid: that path has independence number h, not h-1. Since Lemma 4.2 invokes Lemma 2.4(iii) to rule out l=2h+2, the proof of Theorem 1.10 is unsound as written. The counterexample still contains the h=3 linear forests, so it does not by itself disprove the main theorem, but it invalidates the stated proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":25889,"tokens_out":7139,"duration_ms":66957,"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":[{"comment":"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":"Section 2, Lemma 2.4(iii)"},{"comment":"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.","section":"Section 4, Lemma 4.10 and Theorem 4.11(b)"}],"minor_comments":[{"comment":"The abstract contains a grammatical error: 'extends and strengths' should be 'extends and strengthens'.","section":"Abstract and Introduction"},{"comment":"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.","section":"Theorem 4.11 proof"},{"comment":"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.","section":"Lemma 2.7(iii) proof"},{"comment":"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).","section":"Lemma 4.9 proof"},{"comment":"The statement of Theorem 1.11(b) has a typo: 'δ(G) ≥ h ≥ 2 an k ≥ 1' should read 'δ(G) ≥ h ≥ 2 and k ≥ 1'.","section":"Theorem 1.11(b)"}],"recommendation":"major_revision","confidential_remarks":"The false Lemma 2.4(iii) is not a cosmetic issue: it is used at a critical juncture in Lemma 4.2 to eliminate the l=2h+2 case, and the provided counterexample shows that the stated common-neighborhood conclusion is simply wrong. The authors will need either to correct the lemma under additional hypotheses or to develop a different argument for the l=2h+2 case. Because the main theorems may still be true, I am not recommending rejection, but the revision will need to be substantial. The mismatch between Lemma 4.10 and Theorem 4.11(b) further indicates that the small-h, small-b cases require separate treatment."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nBut 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.\n\nThere 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.\n\nThe 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.","headline":"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.","tokens_in":26423,"tokens_out":7110,"would_cite":false,"duration_ms":68457,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A minimum-degree threshold forces every linear forest into a large connected graph unless the graph belongs to a short list of explicit exceptions.","keywords":["Erdős-Gallai theorem","stability version","minimum degree","linear forest","path embedding","extremal graph theory","2-connected graphs","cut vertex"],"falsifier":"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.","tokens_in":25363,"feed_emoji":"🌲","tokens_out":7406,"duration_ms":70111,"temperature":0.7,"pith_summary":"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.","feed_headline":"Enough minimum degree embeds every linear forest","feed_subtitle":"Resisting graphs must belong to one of a short list of exceptional shapes.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Erdős–Gallai path theorem that motivates the minimum-degree threshold and gives the baseline edge-count condition for containing $P_l$.","marker":"[6]"},{"why":"Supplies the even-path stability result this paper extends: minimum degree $h$ forces $P_{2h+2}$ except for $S_{n,h}$ and $L_{t,h}$.","marker":"[2]"},{"why":"Supplies the odd-path stability result this paper extends: minimum degree $h$ forces $P_{2h+3}$ except for $S^+_{n,h}$ and related exceptional families.","marker":"[9]"},{"why":"Gives the extremal edge-count theorem for linear forests whose extremal graphs $S_{n,h}$ and $S^+_{n,h}$ reappear as the main 2-connected exceptions; also supplies Lemma 2.3 on common neighborhoods.","marker":"[8]"},{"why":"Provides the earlier edge-count stability theorem for paths that this paper's minimum-degree version parallels and strengthens.","marker":"[7]"},{"why":"Supplies Lemma 2.2: a 2-connected graph with minimum degree $h$ contains a cycle of length at least $2h$.","marker":"[5]"},{"why":"Gives, with [6], the classical result that minimum degree $h+1$ in a connected graph forces an odd path $P_{2h+3}$.","marker":"[1]"}],"fun_headline_variants":["Linear forests forced by minimum degree, up to exceptions","Minimum degree threshold for all linear forests, with exceptions","Stability for Erdős-Gallai: linear forests embed unless exceptional","High min degree guarantees linear forests, save rare graphs","Erdős-Gallai stability: min degree forces linear forests"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Linear forests forced by minimum degree, up to exceptions","Minimum degree threshold for all linear forests, with exceptions","Stability for Erdős-Gallai: linear forests embed unless exceptional","High min degree guarantees linear forests, save rare graphs","Erdős-Gallai stability: min degree forces linear forests"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000689,"raw_usage":{"total_tokens":3201,"prompt_tokens":1102,"completion_tokens":2099,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":2026}},"tokens_in":718,"tokens_out":2099,"duration_ms":15318,"temperature":1.0,"reasoning_tokens":2026,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:43:10.819840+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Erd o s and T","cited_arxiv_id":null,"evidence_quote":"Supplies the Erdős–Gallai path theorem that motivates the minimum-degree threshold and gives the baseline edge-count condition for containing $P_l$."},{"cited_title":"Ali and W","cited_arxiv_id":null,"evidence_quote":"Supplies the even-path stability result this paper extends: minimum degree $h$ forces $P_{2h+2}$ except for $S_{n,h}$ and $L_{t,h}$."},{"cited_title":"Lidick\\' y , H","cited_arxiv_id":null,"evidence_quote":"Supplies the odd-path stability result this paper extends: minimum degree $h$ forces $P_{2h+3}$ except for $S^+_{n,h}$ and related exceptional families."},{"cited_title":"Gorgol, Tur\\' a n number for disjoint copies of graphs, Graphs Combin","cited_arxiv_id":null,"evidence_quote":"Gives the extremal edge-count theorem for linear forests whose extremal graphs $S_{n,h}$ and $S^+_{n,h}$ reappear as the main 2-connected exceptions; also supplies Lemma 2.3 on common neighborhoods."},{"cited_title":"u redi, A. Kostochka, J. Verstra\\","cited_arxiv_id":null,"evidence_quote":"Provides the earlier edge-count stability theorem for paths that this paper's minimum-degree version parallels and strengthens."},{"cited_title":"Dirac, Some theorems on abstract graphs, Proc","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.2: a 2-connected graph with minimum degree $h$ contains a cycle of length at least $2h$."},{"cited_title":"Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat","cited_arxiv_id":null,"evidence_quote":"Gives, with [6], the classical result that minimum degree $h+1$ in a connected graph forces an odd path $P_{2h+3}$."}],"review_version":1}