{"id":"fb349c02-4cdd-4e1e-a87c-e60599d8184e","arxiv_id":"2411.17885","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Connected graphs with fewer than 9/4 n - 15/4 edges always have a vertex cut inducing a forest, improving on the previous 11/5 n - 18/5 bound toward the conjectured 3n - 6.","lead":"This paper improves the known edge threshold that forces a forest cut in connected graphs. It also disproves a recent conjecture and provides tight examples for related graph families.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3(a) rests on unproved structural lemmas: Corollary 8, the actual counting premise, is asserted as a deduction from Lemma 7(b)-(c) without proof, making the central bound conditional.","rationale":"I agree with the reader that the central claim is plausible but not fully verifiable from the text. The counting part of Theorem 3(a) is clean, but it relies on Corollary 8, which is the real load-bearing step. Lemma 7 is stated without proof, and the text does not show how Corollary 8 follows. The paper even notes 'Due to space constraints, we omit a few proofs,' so this is acknowledged, but for a referee the consequence is that the theorem is conditional on a non-exhibited structural argument. The omission of Lemma 9 matters for Theorem 3(b)-(c) but not for the strongest claim. The submission-page abstract overstates the bound as 9/4n, while the full text proves 9/4n−15/4; this is a presentation issue, not a correctness issue. No internal algebraic error was found in the displayed counting. Therefore the verdict remains conditional.","tokens_in":5639,"tokens_out":8225,"duration_ms":71518,"concrete_test":"Provide a full proof of Lemma 7(b)-(c) and of the deduction of Corollary 8, tracking the exact argument that Lemma 7(b) forces a K4 around each degree-4 vertex and that this K4 prevents two degree-4 neighbors. If the derivation of Corollary 8(b) needs an assumption beyond Lemma 7 (for instance that the K4-neighbors of a degree-4 vertex have degree ≥5), the counting argument has a hidden premise; if it does not, the missing proofs are only an expositional gap. As a secondary check, exhaustively verify Corollary 8 for all small 4-connected graphs with no forest cut (n≤12) to catch obvious counterexamples.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3(a) depends entirely on the counting via F4, and the two inequalities |F4| ≥ 3n4 and |F4| ≤ Σ_{j≥5}(j−2)nj are justified by Corollary 8(a)-(b). Corollary 8 is asserted to follow from Lemma 7(b)-(c), but neither Lemma 7(b)-(c) nor the derivation of Corollary 8 is included. This is not a cosmetic omission: the inference from 'no degree-4 vertex has a C4 in its neighborhood' plus 'no two degree-4 vertices lie in a common K4' to 'every degree-4 vertex has at most one degree-4 neighbor' and 'every degree-≥5 vertex has at least two degree-≥5 neighbors' requires additional structural argument. For example, Lemma 7(b) is said to imply every degree-4 vertex lies in a K4; if the three K4-neighbors are not constrained to be high-degree, Corollary 8(a) does not obviously follow. Should either part of Corollary 8 fail in a minimum counterexample, the counting chain gives no lower bound on e(G). Thus the central claim is conditionally supported by an unverified local-density premise.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies forest cuts: vertex cuts whose removal leaves a forest. Building on Chernyshev, Rauch, and Rautenbach, who proved that every connected graph on n vertices with fewer than (11/5)n - 18/5 edges has a forest cut, the authors improve the coefficient to 9/4, proving in Theorem 3(a) that every connected n-vertex graph with no forest cut has at least (9/4)n - 15/4 edges. The proof uses a minimal counterexample argument and a counting inequality over the number of edges joining degree-4 vertices to higher-degree vertices. The paper also proves lower bounds for 3-connected 1-cyclic and 2-cyclic graphs in Theorem 3(b) and 3(c), gives tight constructions in Remark 4, and disproves Conjecture 2 of Chernyshev et al.","tokens_in":5839,"tokens_out":6805,"duration_ms":57099,"significance":"If the structural lemmas are correct, the paper is a genuine advance: it improves the leading constant of an extremal bound, provides tight examples showing the new bounds are asymptotically optimal, and refutes a published conjecture. The counting arguments in the proofs of Theorems 3(a)-(c) are clean and parameter-free, and the extremal constructions are concrete and verifiable. However, the main theorem depends on Lemma 7(b)-(c) and Corollary 8, whose proofs are not included, and Theorems 3(b)-(c) depend on Lemma 9, whose proof is also omitted. The paper is not circular and the algebraic steps are internally consistent, but the central claims are conditional on unverified structure statements.","major_comments":[{"comment":"Lemma 7(b) and (c) are stated without proof, and they are load-bearing for Theorem 3(a). The counting chain in the proof of Theorem 3(a) needs |F4| ≥ 3n4 and |F4| ≤ Σ_{j≥5}(j-2)n_j, which are justified only by Corollary 8(a)-(b). Corollary 8 is asserted to follow from Lemma 7(c), but the deduction is not shown. In particular, the sentence 'Lemma 7(b) implies that every degree-4 vertex... lies in a K4' is not immediate from the absence of a C4 in the neighborhood, and the step from 'no two degree-4 vertices are in the same K4' to 'every degree-4 vertex has at most one degree-4 neighbor' requires additional argument. The authors must provide the missing proofs or a precise reference to a full version.","section":"§2, Lemma 7 and Corollary 8"},{"comment":"The paper says Lemma 7(b)-(c) are strengthenings of Chernyshev et al.'s Result [2, Claim 2], which states that every degree-4 vertex has at most two degree-4 neighbors. Corollary 8(a) is strictly stronger: it asserts at most one degree-4 neighbor. A strengthening of this kind is exactly where a minimal-counterexample argument can fail, and the stated text gives no derivation. Since the inequalities |F4| ≥ 3n4 and |F4| ≤ Σ_{j≥5}(j-2)n_j depend on this stronger statement, the proof of Theorem 3(a) is incomplete without it.","section":"§2, Corollary 8(a) versus [2, Claim 2]"},{"comment":"Lemma 9 is explicitly left without proof, yet both Theorem 3(b) and Theorem 3(c) rely on it. Lemma 9(b) is used directly in the counting arguments, and Lemma 9(a) is used in the proof of Lemma 10, which in turn supplies the bound |F| ≥ 2n3 in Theorem 3(c). If Lemma 9(b) fails, the disjunction that drives the 15/8 n and 2n bounds is unsupported. The authors should include the proof of Lemma 9 or state it as a hypothesis and prove the theorems conditionally.","section":"§3, Lemma 9"}],"minor_comments":[{"comment":"The abstract as printed says the improvement gives a forest cut for graphs with fewer than (9/4)n edges, while Theorem 3(a) and the introduction state the threshold as (9/4)n - 15/4. These statements should be made consistent.","section":"Abstract and Introduction"},{"comment":"The statement 'If G is a 3-connected 1-cyclic graph on n ≥ 5 vertices. Then the following hold...' contains a punctuation error; it should read 'If G is a 3-connected 1-cyclic graph on n ≥ 5 vertices, then the following hold...'.","section":"§3, Lemma 9 statement"},{"comment":"In the final counting display, the paper writes 'e(G) ≥ 9n/4, a contradiction.' Since the counterexample satisfies e(G) < (9/4)n - 15/4, the contradiction is clear, but the displayed e(G) ≥ 9n/4 is stronger than the theorem's bound; a one-line clarification would improve readability.","section":"§2, proof of Theorem 3(a)"},{"comment":"Reference [3] is described as containing similar results on 1-cyclic graphs, but the text does not indicate which specific results overlap with those in Section 3. A brief comparison would help the reader understand the novelty.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is an extended abstract for EUROCOMB, so some omitted proofs are customary. For a journal version, however, the omitted proofs of Lemma 7(b)-(c), Corollary 8, and Lemma 9 are essential, and the authors should also clarify their relationship to the independent work in [3]. The central counting argument itself is sound, and the constructions are valuable; the revision should focus on completing the verification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper improves the known forest-cut bound from 11/5 n - 18/5 to 9/4 n - 15/4, and it disproves Conjecture 2 with a concrete infinite family. That is a genuine step toward the Chernyshev-Rauch-Rautenbach conjecture, and the counting argument in the proof of Theorem 3(a) is clean and plausible. The tight constructions in Remarks 4(a)-(d) are concrete and verify, and the paper is honest about the independent work in [3]. So there is real substance here.\n\nThe soft spot is exactly where the stress-test lands. The proof of Theorem 3(a) depends on Corollary 8, which is asserted to follow from Lemma 7(b)-(c). But Lemma 7(b) and (c) are only stated, not proved, and the derivation of Corollary 8 is not shown. This is not a cosmetic omission: the inference from \"no degree-4 vertex has a C4 in its neighborhood\" and \"no two degree-4 vertices lie in a common K4\" to the counting premise \"every degree-4 vertex has at most one degree-4 neighbor\" requires real argument. Without that, the claimed lower bound is conditional on unverified structure. Lemma 9, which drives the 1-cyclic and 2-cyclic bounds, is also omitted. For an extended abstract this is normal, but here the omitted lemmas are load-bearing.\n\nOne more issue: the submission-page abstract says \"less than 9/4 n edges\" while the theorem and the full-text abstract both state 9/4 n - 15/4. That is an overstatement and should be fixed.\n\nIf the missing proofs are supplied, this is a solid contribution. The constructions are explicit, the counting idea is elegant, and the link to Conjecture 1 is meaningful. As it stands, though, the central theorem is not verifiable from the text, and a referee would need the full version or an appendix to check Lemma 7 and Lemma 9.\n\nRecommendation: send it to peer review, but ask the authors to include the omitted proofs or a complete appendix. Not a desk reject — the result matters and the plausibility is high. I would not cite the bounds as proven until the lemmas are public.","headline":"Real new bound and a clean counterexample, but the main proof rests on unproved structural lemmas and the abstract overstates the theorem.","tokens_in":715,"tokens_out":692,"would_cite":false,"duration_ms":22213,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every connected graph on n vertices with fewer than 9n/4 - 15/4 edges has a vertex cut that induces a forest, improving the previous 11n/5 - 18/5 threshold.","keywords":["forest cut","vertex cut","acyclic neighborhood","1-cyclic graph","2-cyclic graph","k-cyclic graph","sparse graphs","extremal graph theory"],"falsifier":"A connected graph on n vertices with no forest cut and fewer than 9n/4 - 15/4 edges would refute Theorem 3(a). For the supporting structure, a minimum counterexample containing a degree-4 vertex whose neighborhood has a C4, or two degree-4 vertices in a common K4, would refute Lemma 7(b) or (c). For the cyclic bounds, a 3-connected 1-cyclic graph on n ≥ 6 vertices with fewer than 15n/8 edges, or a 3-connected 2-cyclic graph with fewer than 2n edges, would refute Theorem 3(b) or (c).","tokens_in":5420,"feed_emoji":"🌲","tokens_out":7145,"duration_ms":52743,"temperature":0.7,"pith_summary":"The paper improves the known threshold for a sparse connected graph to contain a vertex cut that induces a forest. Chernyshev, Rauch, and Rautenbach had shown that fewer than 11n/5 - 18/5 edges forces such a cut; this paper lowers the threshold to 9n/4 - 15/4. The argument works by studying a smallest counterexample, ruling out configurations among degree-4 vertices, and then counting edges by degree. The paper also proves lower bounds on edges for 3-connected graphs whose small vertex sets have a cycle in their neighborhood (1-cyclic and 2-cyclic graphs), and gives constructions showing these bounds are tight. One construction disproves a conjecture of Chernyshev, Rauch, and Rautenbach about graphs with cycles in every vertex neighborhood.","feed_headline":"Forest cut guaranteed below 9n/4 edges","feed_subtitle":"Counting argument improves sparse-graph threshold for vertex cuts that induce forests, toward the 3n-6 conjecture.","key_machinery":"The proof is carried by the concept of a minimum counterexample to the parameterized α-FC Conjecture, which asserts that any connected graph on n vertices with no forest cut has at least α(n-3)+3 edges. For a minimum such graph, Lemma 7 gives structural restrictions: the graph is 4-connected, no degree-4 vertex has a C4 in its neighborhood, and no two degree-4 vertices lie in a common K4. These restrictions, combined with a counting inequality on edges from degree-4 vertices to higher-degree vertices, yield the 9/4 bound. For the 1-cyclic and 2-cyclic results, the key objects are 3-connected graphs in which every set of at most k vertices is dominating or has a cycle in its neighborhood; Lemma 9 and Lemma 10 control the neighbors of degree-3 and degree-4 vertices and feed the same type of degree-counting argument.","core_discovery":"The central claim is Theorem 3(a): if a connected graph on n vertices has no forest cut, then it has at least 9n/4 - 15/4 edges; equivalently, every connected graph with fewer than that many edges has a vertex cut whose removal leaves a forest. This improves the earlier bound 11n/5 - 18/5 and moves toward the conjectured bound 3n - 6. The proof fixes a minimum counterexample, uses structural lemmas to constrain how degree-4 vertices can sit inside the graph, and derives the edge bound by counting edges from vertices of degree at least 5. The paper also establishes tight lower bounds of 15n/8 for 3-connected 1-cyclic graphs and 2n for 3-connected 2-cyclic graphs, with constructions showing both are asymptotically optimal.","pith_inferences":["The parameterized α-FC Conjecture suggests a natural program: prove the threshold for a sequence of α values by progressively strengthening the structural lemmas about degree-4 vertices, and the omitted proofs of Lemma 7(b)-(c) and Lemma 9 are the likely bottleneck for the next improvement.","The replacement constructions (blowing up vertices to K4's or octahedra) likely generalize to k-cyclic graphs for k > 2, producing extremal examples that could calibrate conjectured bounds.","Since the paper notes it barely uses the forest-cut requirement for sets larger than 2, similar counting arguments may apply to weaker 'acyclic neighborhood' conditions and yield better bounds toward Conjecture 1.","A computer search over small graphs could test Conjecture 5 directly: any 4-connected 2-cyclic graph on 9 or 10 vertices with fewer than 7n/3 edges would refute it."],"forward_implications":["If Theorem 3(a) is correct, every connected graph with fewer than 9n/4 - 15/4 edges has a forest cut, improving the previous guarantee of 11n/5 - 18/5 edges.","The constructions in Remark 4 show that the 15n/8 bound for 3-connected 1-cyclic graphs is asymptotically tight, disproving Conjecture 2.","The 2n bound for 3-connected 2-cyclic graphs is tight for the constructed families, with 3-connected examples attaining exactly 9n/4 edges.","If Conjecture 5 holds, namely that every 4-connected 2-cyclic graph on n ≥ 9 vertices has at least 7n/3 edges, it would improve Theorem 3(a) toward the conjectured 3n - 6 bound."],"supporting_citations":[{"why":"Establishes the independent-cut analogue that motivates the forest-cut problem and the conjecture.","marker":"[1]"},{"why":"Supplies the conjecture, the previous 11n/5 - 18/5 bound, and the minimum-counterexample framework (Claims 1, 2, and 3) that Lemma 7 and Corollary 8 strengthen.","marker":"[2]"},{"why":"Provides 3-connected 3-regular graphs used in the construction that disproves Conjecture 2 and proves the asymptotic tightness of Theorem 3(b).","marker":"[4]"}],"fun_headline_variants":["Forest cut guaranteed under 9n/4 edges","Every sparse graph has a forest cut","Improved forest cut bound: below 9n/4","Counting argument raises forest cut threshold","Sparse graphs forced to have forest cuts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes the truth of two structural lemmas stated without proof in the extended abstract: that in a smallest graph with no forest cut and fewer than 9n/4 - 15/4 edges, no degree-4 vertex has a C4 in its neighborhood and no two degree-4 vertices share a K4, and the counting inequality that yields the bound collapses if either fails.","fun_headline_variants_meta":{"raw":{"variants":["Forest cut guaranteed under 9n/4 edges","Every sparse graph has a forest cut","Improved forest cut bound: below 9n/4","Counting argument raises forest cut threshold","Sparse graphs forced to have forest cuts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000219,"raw_usage":{"total_tokens":1378,"prompt_tokens":817,"completion_tokens":561,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":433,"completion_tokens_details":{"reasoning_tokens":493}},"tokens_in":433,"tokens_out":561,"duration_ms":5761,"temperature":1.0,"reasoning_tokens":493,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:45:39.866693+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A connected graph on n vertices with no forest cut and fewer than 9n/4 - 15/4 edges would refute Theorem 3(a). For the supporting structure, a minimum counterexample containing a degree-4 vertex whose neighborhood has a C4, or two degree-4 vertices in a common K4, would refute Lemma 7(b) or (c). For the cyclic bounds, a 3-connected 1-cyclic graph on n ≥ 6 vertices with fewer than 15n/8 edges, or a 3-connected 2-cyclic graph with fewer than 2n edges, would refute Theorem 3(b) or (c).","supporting_citations":[{"cited_title":"A note on fragile graphs","cited_arxiv_id":null,"evidence_quote":"Establishes the independent-cut analogue that motivates the forest-cut problem and the conjecture."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides 3-connected 3-regular graphs used in the construction that disproves Conjecture 2 and proves the asymptotic tightness of Theorem 3(b)."}],"review_version":1}