Sparse graphs with an independent or foresty minimum vertex cut

Kun Cheng; Xingzhi Zhan; Yurui Tang

REVIEW 2 major objections 4 minor 9 references

Sparse graphs with an independent or foresty minimum vertex cut

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · 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 on $n\ge 7$ vertices with at most $\lfloor 3n/2\rfloor$ edges has an independent minimum vertex cut, and at most $2n$ edges forces a foresty minimum cut; both bounds are best possible.

desk verdict Solid extremal graph theory paper with two new sharp thresholds; main gap is the hand-waved n=7 base cases, which are load-bearing but likely repairable. read the letter →

arxiv 2412.03869 v1 pith:G4WOCOAF submitted 2024-12-05 math.CO

Kun Cheng , Yurui Tang , Xingzhi Zhan This is my paper · ORCID

classification math.CO MSC 05C3505C4005C69

keywords fragilegraphminimumvertexcutindependentforestyconnectivityextremaltheorysparsegraphs

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 proves two exact edge thresholds for structured minimum vertex cuts in connected graphs. A minimum vertex cut is a smallest set of vertices whose removal disconnects the graph; it is independent if the cut vertices share no edges, and foresty if the graph induced on them is a forest. The main theorems say that for every $n\ge 7$, a connected graph with at most $\lfloor 3n/2\rfloor$ edges must have an independent minimum vertex cut, and a connected graph with at most $2n$ edges must have a foresty minimum vertex cut. Both thresholds are best possible: for every $n\ge 7$ the authors build $n$-vertex graphs with one more edge whose minimum cuts are all an edge, respectively all a triangle. The result matters because it shows that in sparse graphs the connectivity bottleneck cannot be tangled; it must be realized by a structurally simple separator.

What carries the argument

The proofs are built on induction over the order $n$, with the induction step splitting according to minimum degree. Lemma 5 is the workhorse: if $S$ is a minimum vertex cut of a connected graph, every vertex of $S$ has a neighbor in every component of $G-S$. Lemma 6 handles cubic graphs, showing every connected cubic graph of order at least 8 has an independent minimum vertex cut, and Lemma 9 handles 4-regular graphs, showing every connected 4-regular graph of order at least 7 has a foresty minimum vertex cut. Lemma 8, derived from Menger's theorem, provides that a component of size at least $k$ must receive a $k$-matching from any vertex cut in a $k$-connected graph. The base case $n=7$ is settled by a finite enumeration of the possible structures left after deleting a degree-2 or degree-3 vertex and its closed neighborhood, with the sharpness examples built as $n$-vertex graphs whose unique minimum cuts are an edge or a triangle.

What would settle it

Decisive check: exhaustively enumerate all connected graphs of order 7 with at most 10 edges (and separately at most 14) and verify that every residual graph in the listed base-case classes (the nine possibilities for $F-N[v]$ in Theorem 3 and the three for $M[R]$ in Theorem 4) actually contains the claimed cut; a single miss would disprove the theorem, while a pass would confirm the load-bearing base of the induction.

Watch

Extended reading notes

Core claim

The central claim is that sparsity alone forces minimum vertex cuts to be simple. Theorem 3 states that every connected graph of order $n\ge 7$ with at most $\lfloor 3n/2\rfloor$ edges has a minimum vertex cut $S$ whose induced subgraph $G[S]$ is edgeless, and Theorem 4 states that every connected graph of order $n\ge 7$ with at most $2n$ edges has a minimum vertex cut $S$ with $G[S]$ a forest. The word 'minimum' is essential: earlier results only guaranteed an independent vertex cut of some size under different edge counts, not one of cardinality $\kappa(G)$. The proofs proceed by induction on $n$, with dedicated lemmas for cubic and 4-regular graphs, and the sharpness is demonstrated by explicit constructions in which every minimum cut induces exactly one edge, respectively exactly one triangle.

Load-bearing premise

The load-bearing assumption is the unexpanded finite check at $n=7$: after deleting a degree-2 (or degree-3) vertex and its two (or three) neighbors, the proof lists the possible leftover graphs and asserts that each one contains the required cut; if that list is incomplete or any listed case is wrong, the induction base fails.

Editorial extensions

If this is right

For every connected $n$-vertex graph with $n\ge 7$ and at most $\lfloor 3n/2\rfloor$ edges, there is a set of exactly $\kappa(G)$ vertices whose removal disconnects the graph and which induces no edge.
For every connected $n$-vertex graph with $n\ge 7$ and at most $2n$ edges, there is a minimum vertex cut whose induced subgraph is a forest.
The bounds are best possible: the constructions $G_n$ and $F_n$ show that with one extra edge, a graph can have no independent, respectively foresty, minimum vertex cut.
In the induction, the only graphs requiring separate arguments are cubic graphs and 4-regular graphs; all other cases are reduced to a smaller graph by deleting a degree-2 or degree-3 vertex.
Read together with the earlier fragility results cited in the introduction, the theorems show that the stronger minimum-cut versions still hold with linear edge budgets, namely $\lfloor 3n/2\rfloor$ for independent cuts and $2n$ for foresty cuts.

Reading between the lines

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

By the same induction pattern, one can ask for the largest constant $c$ such that every connected $n$-vertex graph with at most $cn$ edges has a minimum vertex cut whose induced subgraph belongs to a fixed hereditary class; the two theorems provide the values $c=3/2$ for edgeless separators and $c=2$ for forest separators.
The finite base case $n=7$ is small enough for a certified computer check; automating that verification would make the proof fully checkable and reusable for other separator classes.
The extremal graphs $G_n$ and $F_n$ have unique or near-unique minimum cuts, which suggests that near the threshold all bad graphs are rigid; classifying the cut structure of all graphs at the critical edge counts would test that rigidity.
A natural next rung is to replace 'forest' with 'graph of bounded treewidth' or 'graph of bounded arboricity' and look for the corresponding edge threshold; the present results are the first two rungs of such a ladder.

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

Short version: this paper deserves a real referee. Theorems 3 and 4 are genuine new results — exact edge thresholds for forcing a minimum vertex cut that is independent (floor(3n/2)) or foresty (2n). The line from Chen-Yu and Le-Pfender to minimum cuts is natural, and Theorem 4 is the first foresty-minimum-cut extremal result I know. The regular-graph lemmas (Lemma 6 for cubic, Lemma 9 for 4-regular) are nontrivial and the induction steps read as sound. The sharpness constructions for odd/even n in Theorem 3 and the F_n family in Theorem 4 look right, based on the stated edge counts and unique minimum cuts.

The weak spot is exactly where the stress test says: the n=7 bases are asserted, not demonstrated. In Theorem 3, the nine possible shapes for F−N[v] are listed with no derivation, and the notation 'K1∨K3' is ambiguous — if it means the join with a triangle it is K4, which would duplicate K−4; likely an overline was lost and they mean the star K1,3. The list may be correct, but the reader cannot tell from the paper. In Theorem 4, the three cases M[R] ∈ {K2+K1, P3, C3} are disposed of with 'easy to verify' plus an unstated appeal to Lemma 8. That is load-bearing. If any listed case is missing or the claimed cut is not actually a cut, both inductions collapse. A referee should ask for a table or appendix that explicitly exhibits the promised independent/foresty 2-cut or 3-cut for each case.

I should stress that I found no independent error in Lemma 6, Lemma 9, or in the induction arguments themselves. So this is a rigor gap, not a fundamental flaw. The paper is far from a worthless submission; it is a good result with a presentation that is too terse in the one place that matters.

Who is it for: extremal graph theorists and people working on vertex cuts, fragility, and forest cuts. It will be useful as a citation for the new thresholds and the regular-graph lemmas. I would not desk-reject it. Send it to a competent referee with a request to check the base cases carefully. If those checks hold, accept; the author can reasonably be asked to expand the proof.

Recommendation: peer review, yes.

Referee Report

2 major / 4 minor

Summary. The paper proves two extremal results about minimum vertex cuts in sparse connected graphs. Theorem 3 states that every connected graph of order n at least 7 with at most floor(3n/2) edges has an independent minimum vertex cut, and that the edge bound is best possible. Theorem 4 states the analogous result with bound 2n for foresty minimum vertex cuts. The proofs are by induction on n, with auxiliary lemmas for cubic and 4-regular graphs, together with explicit sharpness constructions. The paper also recalls and uses standard facts such as Lemma 5 and a Menger-type matching lemma (Lemma 8).

Significance. If the results are correct, they give clean exact edge thresholds for the existence of structured minimum vertex cuts, extending the earlier Chen-Yu and Le-Pfender results on arbitrary independent cuts to minimum cuts, and contributing the new notion of foresty minimum cuts in the sparse regime. The proof strategy is self-contained and elementary, with no fitted parameters or reliance on prior results of the authors. The main gap is the finite verification of the n=7 induction bases, which is asserted rather than written out; once supplied, I see no obstacle to the main theorems. The sharpness constructions are explicit and have the claimed edge counts, which is a genuine strength.

major comments (2)

[Section 2, Proof of Theorem 3, basis step (n=7)] The basis step is asserted rather than demonstrated. The derivation of the list F−N[v] ∈ {2K1+K2, 2K2, K1+P3, K1+C3, K1∨K3, P4, C4, K1∨(K1+K2), K4−e} is not given, and the sentence 'In each case it is easy to find two nonadjacent vertices which form a vertex cut by using the size condition' suppresses the actual case analysis. This is the entire base of the induction, so a missing case or an incorrect cut in any listed case would invalidate Theorem 3. In addition, the entry 'K1∨K3' is ambiguous: if K3 is the triangle, the graph is K4, whereas the list can be complete only if the intended entry is K1∨\overline{K3}=K1,3. Please replace this paragraph with an explicit derivation of the list from Lemma 5, δ(F)=2 and e(F)≤10, and add a table or short case argument that exhibits an independent 2-cut in every configuration, including all possible cross-edge distributions.
[Section 2, Proof of Theorem 4, basis step (n=7)] The δ(M)=3 part of the basis step is also asserted: after reducing to M[S]=C3, the paper states that for M[R]∈{K2+K1, P3, C3} 'it is easy to verify that the statement holds by applying Lemma 8 in the latter two cases.' No foresty 3-cut is exhibited, and the application of Lemma 8 is not spelled out for any of the three cases. Since this is the complete n=7 base of the second induction, the proof is not self-contained at the induction base. Please provide the omitted verification, ideally as three explicit constructions of the promised foresty minimum vertex cut or as a short uniform argument using Lemma 8.

minor comments (4)

[Section 2, Proof of Theorem 3, sharpness construction] The claims that Gn has a unique minimum vertex cut in the odd case and exactly two minimum vertex cuts in the even case are stated without proof; the edge count is also stated rather than computed. These assertions are needed for the 'best possible' part of Theorem 3, so a short verification would make the lower-bound construction self-contained.
[Section 2, Proof of Theorem 4, sharpness construction] The statement that κ(Fn)=3 and {v1,v2,v3} is the unique minimum vertex cut is asserted as 'easy to see.' Since this supports the sharpness of the bound in Theorem 4, adding a brief justification would improve the exposition.
[Throughout] The text contains several formatting artifacts, including the missing overline in the expression K1∨K3 and apparent spacing errors such as 'indepen dent' and 'g raph.' If these are LaTeX or OCR artifacts, please ensure the final version uses unambiguous notation, especially for complements.
[References] References [5] and [8] are arXiv preprints; if journal versions have appeared, it would be helpful to update the citations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorems 3 and 4 are derived self-contained by induction from standard Menger-based facts and elementary proved lemmas; the only self-citation is contextual and non-load-bearing.

full rationale

The derivation chain of Theorems 3 and 4 is self-contained. Theorem 3 uses induction on the order, Lemma 5 (proved directly from the definition of a minimum vertex cut), Lemma 6 (proved with explicit vertex-cut arguments), and a finite case analysis in the n=7 base step. Theorem 4 uses Lemma 7 (a standard consequence of Menger's theorem), Lemma 8 (proved from Lemma 7), Lemma 9 (proved by exhaustive connectivity cases), and a second induction. No parameter is fitted to data and then renamed as a prediction; no quantitative input is adjusted to force the conclusion. The extremal constructions for sharpness are verified by directly identifying all minimum vertex cuts and checking that each induces an edge or a triangle, so they are not imported from any prior result. The only self-citation is the introductory sentence 'There is a recent work involving independent vertex cuts [6]'; this reference to prior work of one of the authors is purely contextual and supports no statement used in the proofs of Theorems 3 or 4. The base-case assertions 'In each case it is easy to find two nonadjacent vertices which form a vertex cut' and 'it is easy to verify that the statement holds' are unexpanded finite verifications; if one of those verifications were incomplete or wrong, that would be a correctness or rigor gap, not circularity, because the intended verification is based on the already imposed size bounds and Lemma 5, not on the theorem being proved. No circular step can be quoted or exhibited, so the appropriate score is 0.

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

The theorems are proved by induction using standard graph theory facts; there are no fitted constants, no ad hoc assumptions, and no new postulated objects. The only underlying inputs are the definitions of vertex cuts, connectivity, and Menger's theorem.

assumptions (3)

standard math Lemma 5: every vertex in a minimum vertex cut has a neighbor in every component of G-S.
Used in Lemma 6, Lemma 9, and the base case of Theorem 3 as a basic property; it is a standard fact proved in a line or two.
standard math Lemma 7 (from Menger's theorem): in a k-connected graph, disjoint vertex subsets of size at least k are joined by k vertex-disjoint paths.
Invoked in Lemma 8 to guarantee a k-matching between a vertex cut and a component; cited from Bondy-Murty and West.
domain assumption Graphs are finite and simple.
Stated at the start of Section 1; the definitions and theorems rely on this convention.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sparse graphs with an independent or foresty minimum vertex cut." pith.science (2026). https://pith.science/paper/G4WOCOAF

@misc{pith2026241203869,
  author       = {Pith},
  title        = {Pith review of: Sparse graphs with an independent or foresty minimum vertex cut},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G4WOCOAF}},
  note         = {Machine review of arXiv:2412.03869}
}

abstract

A connected graph is called fragile if it contains an independent vertex cut. In 2002 Chen and Yu proved that every connected graph of order $n$ and size at most $2n-4$ is fragile, and in 2013 Le and Pfender characterized the non-fragile graphs of order $n$ and size $2n-3.$ It is natural to consider minimum vertex cuts. We prove two results. (1) Every connected graph of order $n$ with $n\ge 7$ and size at most $\lfloor 3n/2\rfloor$ has an independent minimum vertex cut; (2) every connected graph of order $n$ with $n\ge 7$ and size at most $2n$ has a foresty minimum vertex cut. Both results are best possible.

Figures

Figures reproduced from arXiv: 2412.03869 by the authors.

**Figure 2.** G11 and G12 Gn has order n and size ⌊3n/2⌋ + 1. If n is odd, {v1, v(n+1)/2} is the unique minimum vertex cut of Gn, which induces an edge. If n is even, Gn has exactly two minimum 5 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** F11 and F12 Now for every integer n ≥ 7 we construct a graph Fn of order n and size 2n + 1 such that Fn has no foresty minimum vertex cut. This shows that the size bound 2n in Theorem 4 is best possible. Recall that a chord xy of a cycle D is called a k-chord if the distance between x and y on D is k. Let C : v1v2 . . . vn−1v1 be a cycle of order n − 1. Add 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

9 extracted references · 7 canonical work pages

[1]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244, Springer, 2 008

work page
[2]

Caro and R

Y. Caro and R. Yuster, Graph decomposition of slim graphs, Grap hs Combin., 15(1999), no.1, 5–19

work page 1999
[3]

Chen, R.J

G. Chen, R.J. Faudree and M.S. Jacobson, Fragile graphs with sma ll independent cuts, J. Graph Theory, 41(2002), no.4, 327–341

work page 2002
[4]

Chen and X

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

work page 2002
[5]

Chernyshev, J

V. Chernyshev, J. Rauch and D. Rautenbach, Forest cuts in sp arse graphs, arXiv: 2409.17724, 26 September 2024

arXiv 2024
[6]

Y. Hu, X. Zhan and L. Zhang, Graphs with many independent vert ex cuts, Graphs Combin., 40(2024), no.4, Paper No. 83

work page 2024
[7]

Le and F

V.B. Le and F. Pfender, Extremal graphs having no stable cutse ts, Electron. J. Combin., 20(2013), no.1, Paper 35

work page 2013
[8]

Rauch and D

J. Rauch and D. Rautenbach, Revisiting extremal graphs having no stable cutsets, arXiv: 2412.00337, 30 November 2024

arXiv 2024

Show all 9 references

[9]

West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96

D.B. West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96. 9

Pith tools

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

[1] [1]

Bondy and U.S.R

J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244, Springer, 2 008

work page

[2] [2]

Caro and R

Y. Caro and R. Yuster, Graph decomposition of slim graphs, Grap hs Combin., 15(1999), no.1, 5–19

work page 1999

[3] [3]

Chen, R.J

G. Chen, R.J. Faudree and M.S. Jacobson, Fragile graphs with sma ll independent cuts, J. Graph Theory, 41(2002), no.4, 327–341

work page 2002

[4] [4]

Chen and X

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

work page 2002

[5] [5]

Chernyshev, J

V. Chernyshev, J. Rauch and D. Rautenbach, Forest cuts in sp arse graphs, arXiv: 2409.17724, 26 September 2024

arXiv 2024

[6] [6]

Y. Hu, X. Zhan and L. Zhang, Graphs with many independent vert ex cuts, Graphs Combin., 40(2024), no.4, Paper No. 83

work page 2024

[7] [7]

Le and F

V.B. Le and F. Pfender, Extremal graphs having no stable cutse ts, Electron. J. Combin., 20(2013), no.1, Paper 35

work page 2013

[8] [8]

Rauch and D

J. Rauch and D. Rautenbach, Revisiting extremal graphs having no stable cutsets, arXiv: 2412.00337, 30 November 2024

arXiv 2024