REVIEW 3 major objections 4 minor 1 cited by
Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict Real new bound and a clean counterexample, but the main proof rests on unproved structural lemmas and the abstract overstates the theorem. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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).
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§2, Lemma 7 and Corollary 8] 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.
- [§2, Corollary 8(a) versus [2, Claim 2]] 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.
- [§3, Lemma 9] 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.
minor comments (4)
- [Abstract and Introduction] 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.
- [§3, Lemma 9 statement] 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...'.
- [§2, proof of Theorem 3(a)] 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.
- [References] 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.
Circularity Check
No circularity found: Theorem 3(a)-(c) are derived by explicit counting from structural lemmas, and the cited prior results are external to the authors; omitted proofs create a verification gap, not a self-referential derivation.
full rationale
The central claim, Theorem 3(a), is proved by a counting argument rather than by assuming the conclusion. The proof fixes a minimum counterexample, defines n_i and F4, and derives the chain 3n4 <= |F4| <= sum_{j>=5}(j-2)n_j <= 12e(G)+3n4-27n, ending with e(G) >= 9n/4. This contradicts the counterexample hypothesis e(G) < 9n/4 - 15/4. The target bound is therefore an output of the calculation, not an input. Corollary 8, which supplies the two inequalities on |F4|, is stated as a deduction from Lemma 7(b)-(c); those lemmas are in turn described as strengthenings of claims in Chernyshev, Rauch, and Rautenbach [2]. That prior work is external, not authored by the present paper's authors, so this is ordinary reliance on a cited theorem rather than a self-citation chain. The proofs of Lemma 7(b)-(c) and of the derivation of Corollary 8 are omitted, and Lemma 9 is likewise stated without proof. Those omissions are a real verification gap: if the structural facts are false, the bounds are unsupported. But a missing proof is not circularity: the paper nowhere defines its conclusion in terms of those lemmas, fits a parameter and then 'predicts' the same quantity, or imports a uniqueness theorem from its own prior work. The tightness examples in Remark 4 are constructions and are not used to prove the lower bounds. Accordingly, there are no circular steps to exhibit, and the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption Lemma 7(a): a minimum counterexample to the alpha-FC Conjecture is 4-connected and has at least 8 vertices.
- domain assumption Lemma 7(b): no degree-4 vertex in a minimum counterexample has a C4 in its neighborhood.
- domain assumption Lemma 7(c): no two degree-4 vertices in a minimum counterexample lie in the same K4.
- domain assumption Lemma 9: a 3-connected 1-cyclic graph on n >= 5 vertices has no adjacent degree-3 vertices, and either is K^Delta_{n-3} or every vertex has at least three neighbors of degree at least 4.
Cite this review
Pith. "Pith review of Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs." pith.science (2026). https://pith.science/paper/NY5EX3VW
@misc{pith2026241117885,
author = {Pith},
title = {Pith review of: Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/NY5EX3VW}},
note = {Machine review of arXiv:2411.17885}
}
abstract
Chernyshev, Rauch, and Rautenbach proved that every connected graph on $n$ vertices with less than $\frac{11}{5}n-\frac{18}{5}$ edges has a vertex cut that induces a forest, and conjectured that the same remains true if the graph has less than $3n-6$ edges. We improve their result by proving that every connected graph on $n$ vertices with less than $\frac{9}{4}n$ edges has a vertex cut that induces a forest. We also study weaker versions of the problem that might lead to an improvement on the bound obtained.
Figures
Forward citations
Cited by 1 Pith paper
-
Cyclic Neighborhoods in Digraphs
Every strongly connected digraph with cyclic in/out-neighborhoods has at least 7n/3 arcs; every strongly 2-connected such digraph has at least 8n/3 arcs, and both bounds are tight.
Reference graph
Works this paper leans on
-
[3]
The minimum siz e of a 3-connected locally nonforesty graph
Chengli Li, Yurui Tang, and Xingzhi Zhan. The minimum siz e of a 3-connected locally nonforesty graph. Available at arXiv:2410.23702 , 2024
arXiv 2024
-
[1]
Guantao Chen and Xingxing Yu. A note on fragile graphs. Discrete mathematics , 249(1-3):41–43, 2002
work page 2002
-
[2]
Vsevolod Chernyshev, Johannes Rauch, and Dieter Rauten bach. Forest cuts in sparse graphs. Available at arXiv:2409.17724 , 2024
arXiv 2024
-
[4]
Nicholas C. Wormald. The asymptotic connectivity of lab elled regular graphs. Journal of Combinatorial Theory, Series B , 31(2):156–167, 1981
work page 1981
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.