{"id":"19448a8b-6c57-4f12-8751-ba069efed288","arxiv_id":"2412.00337","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A corrected proof shows that every graph with n vertices and 2n-3 edges and no stable cutset is built from triangles and 6-cycles glued along edges or triangles.","lead":"This paper repairs a gap in a published proof about graphs that cannot be disconnected by removing a stable set of vertices. It confirms the structural characterization of extremal graphs first claimed by Le and Pfender in 2013.","discovery_kind":"replication","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The new proof of Claim 14 rests on unverified Claims 6–13 from Le–Pfender; a hidden error in any of them would invalidate the repair.","rationale":"The reader's weakest assumption identifies exactly the load-bearing point: the new proof inherits Claims 6–13 from [9] without reproducing them. I read the entire new proof of Claim 14 and did not find a clear internal contradiction; the terse steps such as \"the choice of the generating sequence S implies\" appear to be fillable by standard normalization arguments, though they are not written out. The proof is intricate and no machine-checked verification exists, so the residual risk is real. However, reliance on previously published claims is normal in mathematical practice, and the paper explicitly states its scope: filling one identified gap. Therefore the correct verdict remains ACCEPT at moderate confidence, matching the reader's assessment.","tokens_in":7287,"tokens_out":30316,"duration_ms":288139,"concrete_test":"Reconstruct Claims 8, 12, and 13 from [9] using only Theorem 1 and the definitions in Section 2. If all three derivations succeed, the external dependency is sound; if any fails, the proof of Claim 14 needs independent support.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper is a proof-repair of Le and Pfender's Theorem 4, and its own contribution is the proof of Claim 14. That proof does not re-derive the properties of the minimal counterexample G; the text says only: \"The following properties of G are deduced in [9]\" and then lists Claims 6–13. Several of these claims are load-bearing in the new argument. Claim 8 (no K2-cutset or K3-cutset) is used to assert that the identification vertex v belongs to every graph in the generating sequence for G′, which underpins the entire path construction P. Claim 12 is used to assert that y1 and z0 are the only common neighbors of y0 and z1, which justifies the order and size of G′. Claim 13 (no P3-cutset) is used both to force z0 out of all edge identifications and in the final contradiction. Corollary 3 is used to lift a stable cutset from G‴ back to G. If any of these prior claims contains a hidden gap, then Claim 14, and therefore Theorem 4, is not established by this paper. This is a legitimate limitation of a proof-repair article, not an internal inconsistency, but it is the central residual risk.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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].","tokens_in":7500,"tokens_out":39032,"duration_ms":351259,"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":[{"comment":"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":"Section 2, proof of Claim 14, path construction"},{"comment":"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":"Section 2, proof of Claim 14, first paragraph"},{"comment":"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.","section":"Section 2, proof of Claim 14a, C6 cases"}],"minor_comments":[{"comment":"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":"Section 2, proof of Claim 14, opening"},{"comment":"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":"Section 2, definitions"},{"comment":"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":"Section 2, proof of Claim 14c"},{"comment":"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.","section":"Section 2, proof of Claim 14b"},{"comment":"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.","section":"Acknowledgements"}],"recommendation":"major_revision","confidential_remarks":"This is a sincere proof-repair paper. I found no circularity or sign of fabrication. The main issue is that the new proof of Claim 14 contains several load-bearing assertions about the generating sequence that are not actually proved; these are likely repairable with additional details, but the manuscript as it stands is not fully verifiable. The paper's heavy reliance on Claims 6-13 from [9] without re-proof is acceptable if those published claims are correct, but the authors should make the dependence explicit. I recommend major revision rather than rejection because the approach is plausible and the identified gap in the original proof is real."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nThere 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.\n\nWho 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.\n\nMy 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.","headline":"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.","tokens_in":7963,"tokens_out":3679,"would_cite":true,"duration_ms":32085,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C69","05C40","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["stable cutset","independent cut","extremal graph theory","fragile graphs","generating sequence","graph gluing","triangles and six-cycles","structural graph characterization"],"falsifier":"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.","tokens_in":7092,"feed_emoji":"🧩","tokens_out":12573,"duration_ms":104291,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sparse graphs without stable cutsets now fully classified","feed_subtitle":"A repaired proof pins down the 2n-3 edge case: every such graph is glued from triangles and six-cycles.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"States Theorem 4, defines the class Gsc, and supplies the structural statement the paper completes.","marker":"[9]"},{"why":"Provides Claims 6-13 and Corollary 3, which the new proof of Claim 14 invokes without reproducing.","marker":"[9]"},{"why":"Proves the 2n-4 threshold theorem that underlies the minimal-counterexample argument and Corollary 3.","marker":"[3]"}],"fun_headline_variants":["Proof gap in stable cutset classification now closed","Every sparse graph without stable cutsets now classified","Extremal no-stable-cutset graphs fully characterized","Missing proof supplied for stable cutset extremal graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Proof gap in stable cutset classification now closed","Every sparse graph without stable cutsets now classified","Extremal no-stable-cutset graphs fully characterized","Missing proof supplied for stable cutset extremal graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000191,"raw_usage":{"total_tokens":1323,"prompt_tokens":903,"completion_tokens":420,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":370}},"tokens_in":519,"tokens_out":420,"duration_ms":4207,"temperature":1.0,"reasoning_tokens":370,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:28:29.319902+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Le and F","cited_arxiv_id":null,"evidence_quote":"States Theorem 4, defines the class Gsc, and supplies the structural statement the paper completes."},{"cited_title":"Le and F","cited_arxiv_id":null,"evidence_quote":"Provides Claims 6-13 and Corollary 3, which the new proof of Claim 14 invokes without reproducing."},{"cited_title":"Chen and X","cited_arxiv_id":null,"evidence_quote":"Proves the 2n-4 threshold theorem that underlies the minimal-counterexample argument and Corollary 3."}],"review_version":1}