Revisiting Extremal Graphs Having No Stable Cutsets

Dieter Rautenbach; Johannes Rauch

REVIEW 3 major objections 5 minor 1 cited by

Revisiting Extremal Graphs Having No Stable Cutsets

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

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

Pith's one-line read This paper fills the missing proof in the classification of graphs without stable cutsets: every graph with $n$ vertices and at most $2n-3$ edges either has a stable cutset or is glued from triangles and six-cycles.

desk verdict A genuine proof-repair that fills a real gap in Le-Pfender; the repair looks plausible but rests on unverified prior claims and a few under-justified steps. read the letter →

arxiv 2412.00337 v1 pith:XGZMOQ67 submitted 2024-11-30 math.CO

Johannes Rauch , Dieter Rautenbach This is my paper · ORCID

classification math.CO MSC 05C6905C4005C75

keywords stablecutsetindependentcutextremalgraphtheoryfragilegraphsgeneratingsequencegluingtrianglesandsix-cyclesstructuralcharacterization

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 targets a sharp structural threshold: any graph on $n$ vertices with at most $2n-3$ edges either has a stable cutset—a set of pairwise nonadjacent vertices whose removal disconnects the graph—or belongs to a recursively defined family $\mathcal{G}_{sc}$ built by gluing triangles and six-cycles along shared edges or triangles. Earlier work had reduced this characterization to a single unproved claim: in every triangle of a minimal counterexample, at least two vertices must also lie in other triangles. The paper proves that claim in full. The proof identifies two vertices of a hypothetical bad triangle to produce a smaller graph with exactly the boundary number of edges, then analyzes that graph through its generating sequence of triangles and six-cycles. With the gap closed, the extremal theorem stands as a complete proof.

What carries the argument

The central object is a generating sequence for $\mathcal{G}_{sc}$: an ordered list of graphs, each isomorphic to $K_3$ or $C_6$, glued one at a time along a shared $K_2$ or $K_3$. Lemma 2 strengthens the known existence of such sequences by showing that, for any chosen block of the sequence, the whole graph has a generating sequence beginning with that block. In the proof of Claim 14, this lemma lets the authors control how the auxiliary graph $G'$ is assembled, choose the earliest possible appearance of the vertex $y_1$, and then propagate stable sets forward through the sequence (Claim 14a). The cases split according to whether a new block is glued by an edge or by a triangle and whether it is a triangle or a six-cycle; each case is forced into contradiction by the stable-set extension.

What would settle it

A computer search over all graphs with $n$ vertices and exactly $2n-3$ edges, for $n$ up to 12, could check whether every graph without a stable cutset belongs to $\mathcal{G}_{sc}$; any mismatch would refute the completed theorem. Equivalently, within the minimal-counterexample framework, a triangle in which two of its vertices lie in no other triangle, while all of Claims 6-13 hold, would show Claim 14 false and force the proof to break.

Watch

Extended reading notes

Core claim

The paper proves Claim 14: in every triangle of a minimal counterexample, at least two vertices belong to other triangles. Assuming a triangle $xy_0z_0$ whose vertices $y_0$ and $z_0$ lie in no other triangle, the authors identify $y_0$ with a suitable neighbor $z_1$ to obtain a smaller graph $G'$ with exactly $2(|G'|-1)-3$ edges; by minimality $G'$ lies in $\mathcal{G}_{sc}$. Using the strengthened generating-sequence lemma, they arrange a generating sequence for $G'$ that starts with the triangle $xvz_0$ and is minimal in the first index where the vertex $y_1$ appears. They then construct an induced path from $y_1$ to $z_0$ through neighbors of $v$, and use a stable-set extension argument, Claim 14a, to rule out each possible shape of the generating sequence. The path is forced to have length four, and a final identification of its vertices produces a graph whose only cut vertex leads to a $K_2$-, $K_3$-, or $P_3$-cutset in $G$, contradicting the earlier claims. This contradiction establishes Claim 14 and completes the proof of the classification theorem.

Load-bearing premise

The proof of Claim 14 takes the previously established Claims 6-13 and Corollary 3 from the earlier characterization paper as correct without re-proving them; if any of those prior claims has a hidden error, the new proof collapses.

Editorial extensions

If this is right

The extremal theorem is now fully proved: every graph on $n$ vertices with at most $2n-3$ edges either has a stable cutset or belongs to the recursively defined class $\mathcal{G}_{sc}$.
Because the unresolved Claim 14 was the only gap, the completed proof validates the classification exactly at the boundary where the earlier $2n-4$ threshold result is tight.
Lemma 2 is now available as a standalone structural tool: every graph in $\mathcal{G}_{sc}$ admits a generating sequence starting with any specified triangle or six-cycle block.
The vertex-identification reduction used here preserves the property of having no stable cutset while lowering the order, which makes the minimal-counterexample argument work at the $2n-3$ edge count.

Reading between the lines

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

A natural next step, not explored in the paper, is to turn the generating-sequence machinery into a recognition algorithm for $\mathcal{G}_{sc}$; the proof suggests that peeling off triangles and six-cycles in reverse order could decide membership in polynomial time.
The same identification trick might prove analogous extremal classifications for other hereditary cutset properties, such as cutsets that are independent sets of bounded size, where the edge threshold could shift.
Since the proof borrows Claims 6-13 from the earlier characterization without re-deriving them, a fully independent verification of those prior claims would make the completed theorem completely self-contained.
With the theorem repaired, it becomes meaningful to search computationally for graphs with $n$ vertices and $2n-2$ edges that lack stable cutsets; any such graph would show that the $\mathcal{G}_{sc}$ family is not the whole story beyond the proved threshold.

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

The thing to know: this is a proof-repair paper, and a legitimate one. It identifies a specific gap in Le and Pfender's 2013 proof of the stable-cutset characterization for graphs with 2n-3 edges, explains why the original deduction of Claim 14 (in every triangle at least two vertices lie in other triangles) was invalid, and supplies an alternative proof. The theorem itself is not new, but the proof of Claim 14 is.

What I like: the authors are upfront about the gap. The "Explanation of the gap" paragraph is clear: Le and Pfender incorrectly concluded that G' is a 2-tree from the absence of a 3-edge matching cut, ignoring that later identifications can eliminate such cuts. The replacement proof is intricate—it builds a path P through the generating sequence, then uses parity and set X_k to contradict a subclaim—and, on a careful read, the steps mostly hang together. They also add a useful strengthening of the generating-sequence lemma (Lemma 2) to control which piece comes first.

The soft spots are the usual ones for a repair. Claim 14's proof leans on Claims 6–13 from the original paper without re-deriving them. If any of those has a hidden flaw, this paper doesn't independently establish the theorem. That's a real limitation, though not fatal: it's a repair, not a from-scratch proof, and they cite the claims explicitly. More concerning, a few asserted steps are under-justified. The sentence "By Claim 8, the vertex v is involved in every edge or triangle identification within S" transfers a property from G to G' without explanation; and the path construction repeatedly uses "the choice of the generating sequence S implies" that a certain vertex belongs to G'_{i-1} but not G'_{≤i-2}, which is doing a lot of work. These may be fillable with a few sentences, but as written they're places a referee should push.

There is no data, no fitting, no circularity. The minimal-counterexample argument is structurally sound, and the contradiction at the end via Corollary 3 is standard.

Who this is for: anyone working on stable cutsets or extremal graph structure; also anyone who cited Theorem 4 and needs a proof they can trust. It deserves serious refereeing—send it out. If the referee can verify the "choice of S" steps and the transfer of Claim 8, it should be accepted.

My take: it's a solid repair, worth publishing, but I'd want a second pair of eyes on the generating-sequence argument before letting it through.

Referee Report

3 major / 5 minor

Summary. The paper revisits the proof of a theorem of Le and Pfender characterizing the graphs on n vertices with 2n-3 edges and no stable cutset: such a graph either has a stable cutset or belongs to the recursively defined class Gsc. The original proof of Theorem 4 contains a gap in the proof of Claim 14, which asserts that in every triangle of a minimal counterexample G, at least two vertices belong to other triangles. The present paper identifies the precise location of the gap and supplies a proof of Claim 14. The proof starts from a triangle xy0z0 in a minimal counterexample G, identifies y0 with a neighbor z1 of z0 to form a smaller graph G', shows G' lies in Gsc, and then uses a carefully chosen generating sequence of G' to construct an induced path P through the neighbors of the identified vertex. A case analysis over edge and triangle identifications with K3 and C6 yields a stable set that either violates Claim 14a or produces a forbidden cutset, giving the contradiction. The paper concludes that the remainder of the proof of Theorem 4 is unchanged from [9].

Significance. If the proof is correct, the paper closes a genuine gap in a published structural characterization and confirms an extremal result at the boundary n vertices and 2n-3 edges. The paper's strengths are that it locates the gap very precisely, proves the needed strengthening of the generating-sequence lemma (Lemma 2), and gives a substantial case analysis for the missing Claim 14. The main residual risk is not circularity but incompleteness: several properties of the generating sequence are asserted with 'the choice of S implies' rather than proved, and the proof rests on Claims 6-13 from [9], which are not reproduced. These are fixable issues, but they are load-bearing, so the manuscript needs another round of detailed revision before it can be regarded as a reliable proof repair.

major comments (3)

[Section 2, proof of Claim 14, path construction] The three assertions introduced by 'the choice of the generating sequence S implies' are not proved. They are used to guarantee that the next vertex in the backward construction is new in G'_{i-1} (in the triangle and C6-edge cases) or that at least one of u and w is new in G'_{i-1} (in the C6-triangle case). This property is essential for the invariants of the path P, namely that the current path vertex is the only path vertex in G'_i and is not in G'_{\le i-1}. The minimality of k only controls the first appearance of y1; it does not by itself control the first appearance of the other vertices on P. Please provide an explicit exchange argument, or a separate lemma, showing that a generating sequence satisfying these additional properties exists.
[Section 2, proof of Claim 14, first paragraph] The inference 'Since (N_G(y0) \cup N_G(z0)) \setminus \{y0,z0\} is not a stable cutset, there are neighbors y1 of y0 and z1 of z0 such that y1 and z1 are adjacent' is not a logical consequence as written: the set S could be stable and still fail to be a cutset. The missing case should be ruled out. For example, if S is stable, then any vertex outside S \cup \{y0,z0\} would be separated from y0 and z0 by S, making S a stable cutset; if no such vertex exists, then G-\{y0,z0\} is an independent set and \{y0,z0\} is a K2-cutset, contradicting Claims 8 and 9. Without this step the existence of y1 and z1 is not established.
[Section 2, proof of Claim 14a, C6 cases] In the inductive extension of X_k, the sentence 'Note that in the final case, if X_{i-1} does not contain either u or w, then, in the graph G, these two vertices are adjacent to z1 and non-adjacent to y0' is asserted without proof. This adjacency information is exactly what feeds the contradiction when y0 and z1 lie in the same component of G-X_\ell, so the induction hypothesis must be strong enough to imply it for both neighbors of v on any cycle in G'_{\le i} - X_i. The case analysis for this condition should be written out in full.

minor comments (5)

[Section 2, proof of Claim 14, opening] The proof relies on Claims 6-13 from [9] without reproducing them. Because Claim 14 was the discovered gap, it would be helpful to state explicitly where each prior claim is used (e.g., Claim 8 for v belonging to every identification, Claim 12 for the common-neighbor count, Claim 13 for z0 not being in any edge identification) so that the reader can assess the residual risk.
[Section 2, definitions] The terms K2-cutset, K3-cutset, P3-cutset, and 3-edge matching cut are used without definition in this paper; a one-sentence definition or a precise pointer to [9] would improve readability.
[Section 2, proof of Claim 14c] The statement that an induced 5-cycle contradicts G'' being in Gsc is not immediate from the recursive definition, since Gsc contains C6; please add a short proof or citation that no graph in Gsc contains an induced C5.
[Section 2, proof of Claim 14b] The deduction that y_{j-1} is adjacent to z1 and non-adjacent to y0 depends on a parity/alternation structure of the path P that is not stated explicitly. A sentence explaining how the path construction enforces this alternation would help.
[Acknowledgements] The informal sentence 'Since their result is just too beautiful to be false' is out of register for a formal journal article; consider removing or rewriting it.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the paper supplies a new proof of a missing claim, relying on prior external results without assuming the target conclusion.

full rationale

The paper's contribution is a proof of Claim 14 within the proof of Theorem 4, which itself is a gap-filling repair of Le and Pfender's argument. The proof proceeds by contradiction on a minimal counterexample G and uses properties of G stated as Claims 6-13, all of which are explicitly cited as deduced in [9]. These are prior external results, not results of the present paper, and none of them is defined in terms of the conclusion being proved. The construction of the path P, the auxiliary claims 14a-14c, and the final contradiction are carried out within the paper using the generating sequences introduced earlier, and they do not fit any parameter to the target result. Corollary 3 is also taken from [9] and is used only to lift a stable cutset from a modified graph back to G; this is a standard use of an external lemma, not a circular reduction. The only self-citation is reference [12] in the introduction's list of related work, which is not load-bearing for any proof step. The residual risk that some of the external Claims 6-13 contain a hidden error is a correctness concern about the cited literature, not a circularity of this paper's derivation. Therefore no step reduces by construction to the claim it is meant to establish, and no fitted input is renamed as a prediction. The derivation is self-contained relative to the stated external lemmas.

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

No free parameters or invented entities. The proof depends on standard graph theory, the minimal-counterexample method, and the prior results from [9] listed above.

assumptions (3)

domain assumption G is a minimal counterexample to Theorem 4.
The proof proceeds by contradiction assuming a counterexample of minimum order, a standard technique.
domain assumption Claims 6-13 from [9] hold for G.
These properties are cited from [9] and used throughout the proof of Claim 14 without re-derivation.
domain assumption Corollary 3 from [9] holds.
Used in the final part of the proof of Claim 14 to derive a stable cutset in G'''. The corollary is stated as a consequence of Chen-Yu's theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Revisiting Extremal Graphs Having No Stable Cutsets." pith.science (2026). https://pith.science/paper/XGZMOQ67

@misc{pith2026241200337,
  author       = {Pith},
  title        = {Pith review of: Revisiting Extremal Graphs Having No Stable Cutsets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XGZMOQ67}},
  note         = {Machine review of arXiv:2412.00337}
}

abstract

Confirming a conjecture posed by Caro, it was shown by Chen and Yu that every graph $G$ with $n$ vertices and at most $2n-4$ edges has a stable cutset, which is a stable set of vertices whose removal disconnects the graph. Le and Pfender showed that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. Le and Pfender's proof contains a gap, which we fill in the present article.

Figures

Figures reproduced from arXiv: 2412.00337 by the authors.

**Figure 1.** Definition of P for an edge identification with C6. Finally, if G′ i is isomorphic to C6 with the two triangles uvw and abc and the 3-edge matching cut {au, bv, cw}, where u, v, and w belong to G′ ≤i−1 and yj = b, then the choice of the generating sequence S implies that at least one of the two vertices u and w, say u, belongs to G′ i−1 but not to G′ ≤i−2 . Now, setting yj+1 = a and yj+2 = u has the desired properti… view at source ↗

**Figure 2.** Definition of P for a triangle identification with C6. Note that in this final case, the next step of the construction of P ensures yj+3 = w. If i = 1, then, since z0 is not involved in any edge identification, we may assume that yj = x. Now, setting ℓ = j + 1 and yℓ = z0 yields P as desired. This completes the construction of P. If p is odd, then let Xk = {y1, y3, y5, . . . , yp}. By the construction of P, the set … view at source ↗

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

Sparse graphs with an independent or foresty minimum vertex cut
math.CO 2024-12 accept novelty 7.0 of 10

Every connected graph with n≥7 vertices and at most floor(3n/2) edges has an independent minimum vertex cut; every connected graph with n≥7 and at most 2n edges has a foresty minimum vertex cut; both bounds are sharp.

Reference graph

Works this paper leans on

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

[9]

Le and F

V.B. Le and F. Pfender, Extremal graphs having no stable cutse ts, Electronic Journal of Combinatorics 20 (2013) Paper 35, 7

work page 2013
[1]

Brandst¨ adt, F.F

A. Brandst¨ adt, F.F. Dragan, V.B. Le, and T. Szymczak, On sta ble cutsets in graphs, Discrete Applied Mathematics 105 (2000) 39–50

work page 2000
[2]

Chen, R.J

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

work page 2002
[3]

Chen and X

G. Chen and X. Yu, A note on fragile graphs, Discrete Mathematic s 249 (2002) 41–43

work page 2002
[4]

Chv´ atal, Recognizing decomposable graphs, Journal of Gra ph Theory 8 (1984) 51–53

V. Chv´ atal, Recognizing decomposable graphs, Journal of Gra ph Theory 8 (1984) 51–53

work page 1984
[5]

Corneil and J

D.G. Corneil and J. Fonlupt, Stable set bonding in perfect graphs and parity graphs, Journal of Combinatorial Theory. Series B 59 (1993) 1–14

work page 1993
[6]

Klein and C.M.H

S. Klein and C.M.H. de Figueiredo, The NP-completeness of multi-par tite cutset testing, Congressus Numerantium 119 (1996) 217–222

work page 1996
[7]

V.B. Le, R. Mosca, and H. M¨ uller, On stable cutsets in claw-free g raphs and planar graphs, Journal of Discrete Algorithms 6 (2008) 256–276

work page 2008

Show all 13 references

[8]

Kratsch and V.B

S. Kratsch and V.B. Le, On polynomial kernelization for Stable Cut set, arXiv 2407.02086

arXiv
[10]

Le and B

V.B. Le and B. Randerath, On stable cutsets in line graphs, Theo retical Computer Science 301 (2003) 463–475

2003
[11]

D. Marx, B. O’Sullivan, and I. Razgon, Finding small separators in linear time via treewidth reduction, ACM Transactions on Algorithms 9 (2013) Art . 30

2013
[12]

Rauch, D

J. Rauch, D. Rautenbach, and U.S. Souza, Exact and paramet erized algorithms for the independent cutset problem, Lecture Notes in Computer Science 1 4292 (2023) 378–391

2023
[13]

Tucker, Coloring graphs with stable cutsets, Journal of Co mbinatorial Theory

A. Tucker, Coloring graphs with stable cutsets, Journal of Co mbinatorial Theory. Series B 34 (1983) 258–267. 8

1983

Pith tools

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

[1] [9]

Le and F

V.B. Le and F. Pfender, Extremal graphs having no stable cutse ts, Electronic Journal of Combinatorics 20 (2013) Paper 35, 7

work page 2013

[2] [1]

Brandst¨ adt, F.F

A. Brandst¨ adt, F.F. Dragan, V.B. Le, and T. Szymczak, On sta ble cutsets in graphs, Discrete Applied Mathematics 105 (2000) 39–50

work page 2000

[3] [2]

Chen, R.J

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

work page 2002

[4] [3]

Chen and X

G. Chen and X. Yu, A note on fragile graphs, Discrete Mathematic s 249 (2002) 41–43

work page 2002

[5] [4]

Chv´ atal, Recognizing decomposable graphs, Journal of Gra ph Theory 8 (1984) 51–53

V. Chv´ atal, Recognizing decomposable graphs, Journal of Gra ph Theory 8 (1984) 51–53

work page 1984

[6] [5]

Corneil and J

D.G. Corneil and J. Fonlupt, Stable set bonding in perfect graphs and parity graphs, Journal of Combinatorial Theory. Series B 59 (1993) 1–14

work page 1993

[7] [6]

Klein and C.M.H

S. Klein and C.M.H. de Figueiredo, The NP-completeness of multi-par tite cutset testing, Congressus Numerantium 119 (1996) 217–222

work page 1996

[8] [7]

V.B. Le, R. Mosca, and H. M¨ uller, On stable cutsets in claw-free g raphs and planar graphs, Journal of Discrete Algorithms 6 (2008) 256–276

work page 2008