On forest and bipartite cuts in sparse graphs

Alexei Volostnov; Elizaveta Neustroeva; Georgy Sokolov; Ilya I. Bogdanov; Nikolay Russkin; Vsevolod Voronov

REVIEW 3 major objections 3 minor 1 cited by

On forest and bipartite cuts in sparse graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Every connected graph with fewer than $(19n-28)/8$ edges has a forest cut, and fewer than $(80n-134)/31$ edges forces a bipartite cut.

desk verdict Improved thresholds with a serious gap in the red-edge counting; worth refereeing but not ready as written. read the letter →

arxiv 2505.16179 v2 pith:6BBYBOL2 submitted 2025-05-22 math.CO

Ilya I. Bogdanov , Elizaveta Neustroeva , Georgy Sokolov , Alexei Volostnov , Nikolay Russkin , Vsevolod Voronov This is my paper · ORCID

classification math.CO MSC 05C4005C3505C69

keywords vertexcutsforestbipartiteindependentsparsegraphsextremalgraphtheoryseparators

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

The paper asks how sparse a connected graph must be before it is guaranteed to have a vertex cut whose induced subgraph is simple, and it answers with explicit edge-count thresholds. For $n\ge4$ vertices, fewer than $(19n-28)/8$ edges force a forest cut, improving the previously known bounds; fewer than $(80n-134)/31$ edges force a bipartite cut, a case that appears not to have been treated before. Neither result reaches the conjectured sharp threshold of $3n-6$, but the proofs show that any hypothetical counterexample would have to be 4-connected, have minimum degree at least 4, and have a degree-4 subgraph consisting of isolated vertices and edges. The interest is that a purely global count of edges forces local separator structure, the kind of statement that underlies recursive decomposition arguments.

What carries the argument

The machinery is a quality function $q_{\alpha,\beta}(G)=\alpha|G|-e(G)-\beta$ restricted to the line $4\alpha-\beta=6$, together with the family of minimal counterexamples it defines. The argument repeatedly uses separations $(M,L,R)$, partitions of the vertex set with no edges between $L$ and $R$; the quality function is modular across any separation, $q(H)=q(H|_{L\cup M})+q(H|_{R\cup M})-q(H|_M)$, so cuts can be transferred between subgraphs and the whole graph. For forest cuts, an independent cut in the graph left after deleting degree-4 vertices is extended into a forest cut, and an external independent-cut theorem supplies the lower count of edges that drives the contradiction. For bipartite cuts, a maximal independent set $A$ maximizing its boundary, together with a red-edge counting argument on vertices of degree 4 and 5, yields the final linear inequalities.

What would settle it

Enumerate connected graphs for small $n$ and look for one with fewer than $(19n-28)/8$ edges and no forest cut, or fewer than $(80n-134)/31$ edges and no bipartite cut; one example would disprove the corresponding theorem. On the structural side, a minimal counterexample with a degree-3 vertex would contradict Lemma 6 and invalidate the proof.

Watch

Extended reading notes

Core claim

The central discovery is that the edge thresholds for the two cut classes can be pushed to $(19n-28)/8$ and $(80n-134)/31$, respectively, through a uniform minimal-counterexample analysis. The proof works with a quality function $q_{\alpha,\beta}(G)=\alpha|G|-e(G)-\beta$ on the parameter line $4\alpha-\beta=6$, and characterizes any smallest graph that has positive quality and no $\Psi$-cut for $\Psi$ the class of forests or bipartite graphs. Such a graph must be 4-connected, have minimum degree at least 4, and have a neighborhood of each degree-4 vertex isomorphic to $T_0$ or $T_1$, the two 4-vertex graphs consisting of a triangle plus an isolated or pendant vertex; in the forest case its degree-4 vertices induce a matching. Substituting the chosen parameter pairs turns the structural constraints into a linear system, and the system is infeasible, which rules out the counterexample.

Load-bearing premise

Both main proofs invoke, without proof, the external theorem that every graph on $n$ vertices with at most $2n-4$ edges has an independent cut; the edge-counting contradictions collapse if that theorem is false.

Editorial extensions

If this is right

Every connected graph with $e(G)<(19n-28)/8$ has a forest cut, and every graph with $e(G)<(80n-134)/31$ has a bipartite cut.
The forest-cut bound improves on the previously published thresholds of $(11n-18)/5$, $(9n-15)/4$, and $|E|\le 2n$.
Because forests are bipartite, Theorem 2 also yields a bipartite cut under the forest threshold, but Theorem 3 guarantees bipartite cuts for graphs with significantly more edges.
Any minimal counterexample would have to be 4-connected with minimum degree at least 4, so the proof rules out all graphs whose structure is too simple to carry a counterexample.

Reading between the lines

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

A natural extension is to run the same machinery on other hereditary cut classes closed under gluing along edges, such as graphs of bounded treewidth, where the modularity identity would still apply.
The bipartite threshold $80/31\approx2.58$ sits closer to the conjectured $3$ than the forest threshold $19/8=2.375$, suggesting that bipartiteness is structurally easier to force; using the bipartite structural lemmas to improve the forest bound is a plausible next step.
An exhaustive check for $n\le12$ could test whether the constants $19/8$ and $80/31$ are tight or whether the structural lemmas leave room to raise them.

Share X Bluesky LinkedIn Reddit HN

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

Bottom line: this is a real advance on both the forest-cut and bipartite-cut thresholds. The forest-cut bound is improved to (19n-28)/8, and the bipartite-cut bound (80n-134)/31 appears to be the first linear bound of its kind. The minimal-counterexample framework is mostly clean, the structural lemmas about degree-4 vertices are genuinely new, and I checked the weighted-sum arithmetic in both theorems—it works as written, given the stated red-edge counts.

The soft spots are real but narrower than the stress-test suggests. Observation 3 (red-edge counts for degree-4 vertices in A) is simply asserted, no proof. That is load-bearing for Corollary 4. Lemma 21 also has a genuine gap: the opening claim that every u in A has at least one red edge is only justified when deg(u) <= 5, because the exchange argument increases e(A,B) by deg(v)+deg(w)-2-deg(u), and with degrees at least 4 that is positive only when deg(u) <= 5. No upper bound on degrees in A is proved. The rest of Lemma 21 only treats the degree-5 case, so the claim for higher-degree vertices is unsupported.

Where the stress-test overreaches is in saying the contradiction collapses without the k-x-y term. I redid the algebra dropping that term: the weighted sum still yields 31e >= 80n - 93, which is strictly greater than 80n - 134. So the theorem might survive a weaker red-edge bound, but the proof as written still relies on an unproved assertion. These are fixable, but they need to be fixed.

The use of the Chen-Yu theorem as a black box is fine; it is external, cited, and not self-referential. The citation pattern looks standard.

Who this is for: people working on sparse graph separators and extremal cut problems. It deserves a serious referee, not a desk reject. My advice: send it out, but tell the authors the red-edge lemmas need complete proofs or the relevant statements need to be restricted and the final inequality rechecked accordingly.

Referee Report

3 major / 3 minor

Summary. The paper studies sufficient edge-density conditions for a connected graph to contain a vertex cut whose induced subgraph is a forest or bipartite. It proves Theorem 2 (a forest cut exists when e < (19n-28)/8) and Theorem 3 (a bipartite cut exists when e < (80n-134)/31), improving on earlier bounds and falling short of the conjectured 3n-6 threshold. The method is to analyze a minimal counterexample through a parametrized quality function q_{alpha,beta}, derive structural restrictions on cuts of size at most four and on degree-4 vertices, and then combine edge-count inequalities with fixed nonnegative weights. The forest-cut part is largely self-contained, while the bipartite-cut part relies on an external theorem of Chen and Yu and on several red-edge counting statements in Section 6.

Significance. If correct, the forest-cut threshold improves the previous bounds collected in the introduction, and the bipartite-cut statement appears to be new. The paper is clearly organized, and the final contradictions are explicit weighted sums with parameters chosen on the line 4alpha-beta=6 rather than fitted to data, which is a genuine strength. The proofs are mostly self-contained apart from the cited Chen-Yu theorem. However, the bipartite section contains unproved or incompletely justified assertions, notably Observation 3 and the opening step of Lemma 21, and these are load-bearing for Theorem 3. The result is plausible, but the proof as written is not complete.

major comments (3)

[Section 6, Lemma 21] The first sentence of the proof asserts that every u in A has at least one red edge, but the exchange argument given for this assertion is valid only when deg(u) <= 5. If u has non-adjacent neighbors v,w in B, the proposed replacement A <- (A\{u}) union {v,w} changes m by deg(v)+deg(w)-2-deg(u); since Corollary 1 gives only deg(v),deg(w) >= 4, this quantity need not be positive when deg(u) >= 6. No upper bound on the degree of vertices in A is established, and the rest of Lemma 21 treats only the degree-5 case. This gap is load-bearing because Corollary 4 adds one red edge for each of the k-x-y vertices of degree at least 6 in A; without that summand, Lemma 22 and the final weighted sum in the proof of Theorem 3 lose the k-x-y term, and the displayed contradiction no longer follows.
[Section 6, Observation 3] Observation 3 is stated without proof and is used in Corollary 4 to obtain the terms 3z and 4(x-z). It is not immediate from the preceding facts: for a degree-4 vertex u in A with no degree-4 neighbor, one must show that every neighbor has degree greater than 4 (or otherwise has another neighbor in A), which in turn relies on Observation 2. But Observation 2's exchange only gives a non-negative change when deg(v)=deg(u)+1, e.g. deg(v)=5 and deg(u)=4, so the claim that the replacement 'increases' e(A,B) is not justified as written. Since Observation 3 supplies the coefficients that make the final weighted sum positive, this is another load-bearing gap.
[Section 6, Lemma 21, cases 3-5] The case analysis in Lemma 21 contains several unsupported assertions. For example, in Case 3 the set M'={v,v2,u3,u4} is declared to be a bipartite cut because 'only two possible edges' vv2 and u3u4 exist, but the text does not justify why edges such as v-u3, v-u4, v2-u3, or v2-u4 are absent under the preceding definitions. Similarly, the phrase 'by similar reasoning' is used where a formal exchange argument is needed. These details matter because Lemma 21 is the only source of the lower bound on the number of red edges, and without that bound the proof of Theorem 3 collapses.

minor comments (3)

[Section 5, proof of Theorem 2] In the displayed inequality for e(G'), the expression 'e(G|M)' should read 'e(G|U)'; the symbol M has not been defined at that point.
[Throughout] There are several typos: 'graphsn' in the abstract, 'Acknowlegments' in the acknowledgments section, and 'Techology' in the affiliations. These should be corrected in revision.
[Section 6, Observation 2] The statement that replacing u by v in A 'increases' e(A,B) is stronger than what the displayed exchange proves; if the proof is repaired, the wording should be changed to 'non-decreasing, and strictly increasing after a possible expansion' or an equivalent formulation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation is self-contained given the external Chen-Yu theorem and no fitted parameter is relabeled as a prediction.

full rationale

The paper proves new sufficient edge bounds for forest and bipartite cuts by analyzing a minimal counterexample G with q(G) = α|G| - e(G) - β > 0. The constants α and β are not fitted to the target result; they are introduced symbolically on the line 4α - β = 6 and later specialized to (19/8, 28/8) and (80/31, 134/31) for the two theorems. The final contradictions are obtained from degree-counting inequalities and red-edge counting, not from assuming the theorem. The only substantial imported result is Theorem 1 of Chen and Yu (2002), which is cited as an external theorem and is used to lower-bound edges in graphs without an independent cut; it is not authored by the present authors, and it does not imply the forest or bipartite cut conclusions by itself. There is no self-citation chain carrying a load-bearing premise, and no quantity is defined in terms of the outcome it is supposed to predict. Any internal proof gaps in Lemma 21 are correctness concerns, not circularity, and therefore do not affect the circularity score.

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

The central claims rest on standard graph theory and on the external Chen-Yu theorem for independent cuts. The parameters α and β are fixed constants chosen to satisfy the structural condition 4α-β=6; they are not fitted to empirical data. No new entities are introduced.

free parameters (4)

α (forest-cut theorem) = 19/8
Chosen to satisfy 4α-β=6 and to make the weighted-sum contradiction in Theorem 2 work; not fitted to any graph data.
β (forest-cut theorem) = 28/8
Determined from α by the relation β=4α-6, enforced throughout the structural lemmas.
α (bipartite-cut theorem) = 80/31
Chosen to make the weighted-sum contradiction in Theorem 3 work and to satisfy the structural condition 2<α≤3.
β (bipartite-cut theorem) = 134/31
Derived from α via β=4α-6, consistent with the paper's parameter family.

assumptions (3)

standard math Forests and bipartite graphs are hereditary and closed under gluing along an edge (Observation 1).
Used in Lemma 7 and Lemma 8 to conclude that combining two Ψ-cuts produces a Ψ-cut.
domain assumption Theorem 1 (Chen and Yu, 2002): every graph on n vertices with at most 2n-4 edges has an independent cut.
Invoked as a black box in the proofs of Theorem 2 and Lemma 18 to lower-bound edges when no independent cut exists.
domain assumption The graph is simple, connected, and has n≥4 vertices (stated in the introduction).
These are the baseline hypotheses for all theorems and the minimal-counterexample definition.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On forest and bipartite cuts in sparse graphs." pith.science (2026). https://pith.science/paper/6BBYBOL2

@misc{pith2026250516179,
  author       = {Pith},
  title        = {Pith review of: On forest and bipartite cuts in sparse graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6BBYBOL2}},
  note         = {Machine review of arXiv:2505.16179}
}

abstract

The paper is devoted to sufficient conditions for the existence of vertex cuts in simple graphs, where the induced subgraph on the cut vertices belongs to a specified graph class. In particular, we show that any connected graph with $n$ vertices and fewer than $(19n - 28)/8$ edges admits a forest cut. This result improves upon recent bounds, although it does not resolve the conjecture that the sharp threshold is $3n - 6$ (Chernyshev, Rauch, Rautenbach, 2024). Furthermore, we prove that if the number of edges is less than $(80n-134)/31$, then the graph admits a bipartite cut.

Figures

Figures reproduced from arXiv: 2505.16179 by the authors.

**Figure 2.** Shortening the path in Lemma 2. The cut vertices are colored red. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Connected components in Lemma 3. the segment between the first and last intersection with M (if necessary) and add a path from u to v in H|(L∪M)\SL , to get a path between them in H|(L∪M)\SL . This contradicts that SL is a cut of H|L∪M. Similarly, u and v lie in different connected components of H|(R∪M)\SR ( [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Cycle on the vertices of the cut in Lemma 8. [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

**Figure 5.** Figure 5: Neighborhoods of u and v in Lemma 12. Proof. Suppose the contrary. Let u, v be degree-4 vertices lying in K4 ⊂ G. Let w1, w2 be the other two vertices of K4, u ′ the fourth neighbor of u, and v ′ the fourth neighbor of v (we allow u ′ = v ′ ). Let L = {u, v}, M = {w1, …

**Figure 6.** Figure 6: Adding two adjacent degree-4 vertices in Lemma 13. [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Cyclic Neighborhoods in Digraphs
math.CO 2026-07 conditional novelty 6.0 of 10

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

15 extracted references · 15 canonical work pages · cited by 1 Pith paper

[1]

N. Alon, P. Seymour, and R. Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 293–299, 1990

work page 1990
[2]

Bollob´ as.Modern graph theory, volume 184

B. Bollob´ as.Modern graph theory, volume 184. Springer Science & Business Media, 2013

work page 2013
[3]

Bonsma, A

P. Bonsma, A. M. Farley, and A. Proskurowski. Extremal graphs having no matching cuts.Journal of Graph Theory, 69(2):206–222, 2012

work page 2012
[4]

Botler, Y

F. Botler, Y. S. Couto, C. G. Fernandes, E. F. de Figueiredo, R. G´ omez, V. F. dos Santos, and C. M. Sato. Extremal problems on forest cuts and acyclic neighborhoods in sparse graphs, 2024

work page 2024
[5]

Caro and R

Y. Caro and R. Yuster. Graph decomposition of slim graphs.Graphs and Combinatorics, 15(1):5–19, 1999

work page 1999
[6]

G. Chen, R. J. Faudree, and M. S. Jacobson. Fragile graphs with small independent cuts. Journal of Graph Theory, 41(4):327–341, 2002

work page 2002
[7]

Chen and X

G. Chen and X. Yu. A note on fragile graphs.Discrete mathematics, 249(1-3):41–43, 2002

work page 2002
[8]

Cheng, Y

K. Cheng, Y. Tang, and X. Zhan. Sparse graphs with an independent or foresty minimum vertex cut, 2024

work page 2024

Show all 15 references

[9]

Chernyshev, J

V. Chernyshev, J. Rauch, and D. Rautenbach. Forest cuts in sparse graphs, 2024

2024
[10]

Fox and J

J. Fox and J. Pach. A separator theorem for string graphs and its applications. Combinatorics, Probability and Computing, 19(3):371–390, 2010. 23

2010
[11]

J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus.Journal of Algorithms, 5(3):391–407, 1984

1984
[12]

R. J. Lipton and R. E. Tarjan. Applications of a planar separator the- orem. In18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 162–170. IEEE, 1977

1977
[13]

Pfender and V

F. Pfender and V. B. Le. Extremal graphs having no stable cutset.The Electronic Journal of Combinatorics, pages P35–P35, 2013

2013
[14]

Rauch and D

J. Rauch and D. Rautenbach. Revisiting extremal graphs having no stable cutsets, 2024

2024
[15]

A. L. Rosenberg and L. S. Heath.Graph separators, with applications. Springer Science & Business Media, 2005. 24

2005

Pith tools

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

[1] [1]

N. Alon, P. Seymour, and R. Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 293–299, 1990

work page 1990

[2] [2]

Bollob´ as.Modern graph theory, volume 184

B. Bollob´ as.Modern graph theory, volume 184. Springer Science & Business Media, 2013

work page 2013

[3] [3]

Bonsma, A

P. Bonsma, A. M. Farley, and A. Proskurowski. Extremal graphs having no matching cuts.Journal of Graph Theory, 69(2):206–222, 2012

work page 2012

[4] [4]

Botler, Y

F. Botler, Y. S. Couto, C. G. Fernandes, E. F. de Figueiredo, R. G´ omez, V. F. dos Santos, and C. M. Sato. Extremal problems on forest cuts and acyclic neighborhoods in sparse graphs, 2024

work page 2024

[5] [5]

Caro and R

Y. Caro and R. Yuster. Graph decomposition of slim graphs.Graphs and Combinatorics, 15(1):5–19, 1999

work page 1999

[6] [6]

G. Chen, R. J. Faudree, and M. S. Jacobson. Fragile graphs with small independent cuts. Journal of Graph Theory, 41(4):327–341, 2002

work page 2002

[7] [7]

Chen and X

G. Chen and X. Yu. A note on fragile graphs.Discrete mathematics, 249(1-3):41–43, 2002

work page 2002

[8] [8]

Cheng, Y

K. Cheng, Y. Tang, and X. Zhan. Sparse graphs with an independent or foresty minimum vertex cut, 2024

work page 2024