{"id":"ef4d8e0c-bbc0-4b42-8e13-6e95407fa991","arxiv_id":"2505.16179","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Any connected graph with fewer than (19n-28)/8 edges has a forest cut, and any graph with fewer than (80n-134)/31 edges has a bipartite cut.","lead":"This paper proves new edge-count thresholds that guarantee a sparse graph contains a vertex cut inducing a forest or a bipartite subgraph. The forest-cut bound improves recent results, and the bipartite-cut bound is apparently the first of its kind.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 21's proof that every u∈A has a red edge only works when deg(u)≤5; no degree bound is proved, so Corollary 4 is unsupported.","rationale":"The paper's overall framework is coherent, and the final weighted-sum arithmetic in both theorems is checkable. The reader's conditional verdict is appropriate. I would not base the main concern on the black-box use of Theorem 1, since that is a standard external theorem; instead, the weakest internal step is Lemma 21's initial exchange argument. It claims a red edge for every vertex of A, but the displayed change in e(A,B) can be zero or negative when deg(u)≥6, and no per-vertex degree bound has been proved. Since Corollary 4 and the final bipartite contradiction depend on exactly this count, the proof is incomplete as written. This does not make the result false; it makes it conditional on supplying a valid argument or an additional structural lemma. I therefore keep the reader's CONDITIONAL verdict and recommend that the authors fill this gap before final acceptance.","tokens_in":12548,"tokens_out":42124,"duration_ms":375772,"concrete_test":"Check the missing degree bound by a direct proof or a counterexample: enumerate all graphs satisfying the established necessary conditions of a bipartite minimal counterexample (min degree ≥4, no cut of size <4, no K4/D/C4 cuts, no bipartite cut, q_{80/31,134/31}>0) on up to 14 vertices, with A a maximum-boundary independent set, and test whether any degree-6 or higher vertex in A has no red incident edge. If such a graph appears, Lemma 21 is false; if none appears, extract the structural reason and add it to the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 6, Lemma 21 begins by asserting that every u∈A has at least one red edge. Given non-adjacent v,w∈N(u), the proposed exchange A←(A\\{u})∪{v,w} changes e(A,B) by deg(v)+deg(w)−2−deg(u). The proof only cites deg(v),deg(w)≥4 (Corollary 1), so the increase is positive only when deg(u)≤5. No upper bound on degrees in the minimal counterexample is established: q(G)>0 gives only an average-degree bound, and Corollary 1 is a minimum-degree statement. Thus the assertion is unproved for vertices of degree at least 6 in A. This is load-bearing because Corollary 4 adds k−x−y red edges, one for each degree-≥6 vertex in A; without that term, Lemma 22 and Corollary 5 lose the −3y cancellation in the final weighted sum, and the contradiction in Theorem 3 no longer follows. The later part of Lemma 21 treats only the degree-5 case, so it cannot supply the missing argument for higher-degree vertices. This is an internal proof gap, not a disagreement with external results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1455,"tokens_out":1574,"duration_ms":181227,"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":[{"comment":"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":"Section 6, Lemma 21"},{"comment":"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":"Section 6, Observation 3"},{"comment":"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.","section":"Section 6, Lemma 21, cases 3-5"}],"minor_comments":[{"comment":"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.","section":"Section 5, proof of Theorem 2"},{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 6, Observation 2"}],"recommendation":"major_revision","confidential_remarks":"The forest-cut part of the paper appears sound, and the overall approach is promising. My main concern is the red-edge counting machinery in Section 6: Observation 3 is unproved, and Lemma 21's proof does not cover degree-6+ vertices in A, although Corollary 4 requires exactly that. These are internal proof gaps rather than disagreements with external results. If the authors can supply a correct proof of the red-edge lower bound, the paper should be publishable; as written, Theorem 3 is not established. I saw no concerns about attribution or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nWhere 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.\n\nThe 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.\n\nWho 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.","headline":"Improved thresholds with a serious gap in the red-edge counting; worth refereeing but not ready as written.","tokens_in":13380,"tokens_out":6913,"would_cite":false,"duration_ms":56597,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C40","05C35","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["vertex cuts","forest cuts","bipartite cuts","independent cuts","sparse graphs","extremal graph theory","graph separators"],"falsifier":"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.","tokens_in":12364,"feed_emoji":"🌲","tokens_out":8317,"duration_ms":69967,"temperature":0.7,"pith_summary":"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.","feed_headline":"New edge thresholds force forest and bipartite cuts","feed_subtitle":"Below (19n−28)/8 edges every connected graph splits at a cut inducing a forest; a second bound covers bipartite cuts.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Theorem 1, the independent-cut theorem used to force edge lower bounds in both main proofs.","marker":"[7]"},{"why":"States Conjecture 1, defines the $3n-6$ target, and gives the earlier forest-cut threshold $(11n-18)/5$ that this paper improves.","marker":"[9]"},{"why":"Provides the previous forest-cut bound $(9n-15)/4$ that Theorem 2 surpasses.","marker":"[4]"},{"why":"Provides the earlier $|E|\\le 2n$ forest-cut result that Theorem 2 improves.","marker":"[8]"}],"fun_headline_variants":["Forest cuts below (19n−28)/8, bipartite below (80n−134)/31","Sparse graphs: new edge thresholds force forest and bipartite cuts","Tighter edge bounds guarantee forest and bipartite cuts","Improving thresholds for forest and bipartite vertex cuts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Forest cuts below (19n−28)/8, bipartite below (80n−134)/31","Sparse graphs: new edge thresholds force forest and bipartite cuts","Tighter edge bounds guarantee forest and bipartite cuts","Improving thresholds for forest and bipartite vertex cuts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000588,"raw_usage":{"total_tokens":2716,"prompt_tokens":859,"completion_tokens":1857,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":1780}},"tokens_in":475,"tokens_out":1857,"duration_ms":13071,"temperature":1.0,"reasoning_tokens":1780,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:06:42.366876+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Chen and X","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 1, the independent-cut theorem used to force edge lower bounds in both main proofs."},{"cited_title":"Chernyshev, J","cited_arxiv_id":null,"evidence_quote":"States Conjecture 1, defines the $3n-6$ target, and gives the earlier forest-cut threshold $(11n-18)/5$ that this paper improves."},{"cited_title":"Botler, Y","cited_arxiv_id":null,"evidence_quote":"Provides the previous forest-cut bound $(9n-15)/4$ that Theorem 2 surpasses."},{"cited_title":"Cheng, Y","cited_arxiv_id":null,"evidence_quote":"Provides the earlier $|E|\\le 2n$ forest-cut result that Theorem 2 improves."}],"review_version":1}