{"id":"92f43c33-718b-4e1e-af82-d531f4ce17e9","arxiv_id":"2411.09791","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every strongly 2-connected digraph can be generated from the digraph A4 and bidirected cycles by basic, chain, collarette, and bracelet augmentations, and any two such digraphs linked by a butterfly-minor are connected by a sequence of these operations.","lead":"This paper proves that every strongly 2-connected digraph can be built from a small base family by four explicit operations, and that any two such digraphs related by butterfly-minors are connected by a chain of these operations. It is the directed analogue of Seymour's classical splitter theorem for 3-connected graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2's 'exactly one' trichotomy is not established: the proof that no switching path is bad relies on an acyclicity implication that may fail when u≠v.","rationale":"The reader's weakest assumption was Lemma 4.2's trichotomy of H'-ear paths, and my analysis agrees that this is the pivotal combinatorial step. My concern sharpens the reader's: the exhaustiveness portion of Lemma 4.2 appears internally consistent, but the disjointness proof contains a specific, checkable gap. The claimed implication from [S3] to acyclicity of the unions involving S_in_u and S_out_v is not justified for u≠v, and if false it would undermine later uses of the trichotomy in Lemmas 6.4-6.6 and Theorem 1.2. The rest of the paper—augmentation definitions, preservation of strong 2-connectivity, and the overarching induction—does not exhibit an obvious flaw, and the reliance on Wiederrecht's theorem is not circular. However, because the central argument hinges on a classification that is asserted rather than rigorously established at exactly one point, I recommend conditional acceptance: the proof should be accepted only after the trichotomy is mechanically verified or the gap in Lemma 4.2 is repaired.","tokens_in":37729,"tokens_out":37889,"duration_ms":345541,"concrete_test":"Write a brute-force checker for Lemma 4.2 over all small instances: enumerate all strongly 2-connected digraphs D and H with at most 5 vertices, all H-expansions H'⊆D, and all H'-ear paths; using the literal definitions of Section 4.1, compute whether each path is switching, bad, and/or augmenting. Accept the lemma only if every path is in at least one and at most one category. A single path classified as both switching and bad, or in no category, disproves the trichotomy.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Lemma 4.2 asserts that for an H'-switching path P with respect to (u,v), the digraphs S_in_u ∪ S_out_u ∪ P and S_in_v ∪ S_out_v ∪ P are acyclic 'by [S3]'. However, condition [S3] only gives acyclicity of S_out_u ∪ S_in_v ∪ {e : head(e)∈V(S_in_v), tail(e)∈V(S_out_u)} ∪ P. For u≠v this set omits S_in_u and S_out_v, so a directed cycle in S_in_u∪S_out_u∪P (or in S_in_v∪S_out_v∪P) need not appear in [S3]'s set. Such a cycle would make P both H'-switching and H'-bad, contradicting the claimed 'exactly one' classification. This disjointness part of the trichotomy is load-bearing: Lemma 6.4 Claim 1 uses Lemma 4.2 to classify every non-augmenting ear path as bad or non-parallel switching, and Theorem 1.2 Case 5 uses statement (4) to infer that every ear path is parallel switching or bad. If a path can be both switching and bad, these later inferences are not justified, and the inductive construction of the augmentation sequence is not fully proved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a splitter/generation theorem for strongly 2-connected digraphs under the butterfly-minor relation. The main result (Theorem 1.2) states that whenever H is a strongly 2-connected butterfly-minor of a strongly 2-connected digraph D, there is an interpolation sequence from H to D in which each intermediate digraph is strongly 2-connected and each step is one of four local augmentations: basic, chain, collarette, or bracelet. Combined with Wiederrecht's theorem that every strongly 2-connected digraph contains a member of the base family B2 as a butterfly-minor, this yields a generative description of all strongly 2-connected digraphs from B2 (Theorem 1.1). The proof is by induction on |E(D)|-|E(H)|, with the induction step reduced to showing that every H-expansion in D contains a subgraph that is an expansion of an H-augmentation; the central technical device is a classification of ear paths into augmenting, bad, and switching paths.","tokens_in":38000,"tokens_out":23171,"duration_ms":225706,"significance":"If the main theorem is correct, this is a substantial structural result: a splitter theorem for strongly 2-connected digraphs in the butterfly-minor order, with a concise explicit base family and four fairly local operations. The paper clearly explains why an operation adding an unbounded number of vertices in one step is unavoidable, namely the existence of infinite anti-chains of bidirected paths under butterfly-minors. The proof is modular and carefully organized, with many auxiliary lemmas, and the reliance on Wiederrecht's published base-minor theorem is explicit. However, the present version contains a genuine gap in the proof of the ear-path trichotomy (Lemma 4.2); this must be repaired before the proof can be accepted as written.","major_comments":[{"comment":"The disjointness part of the trichotomy is not proved. The text claims that for an H′-switching path P with respect to (u,v), condition [S3] implies that S^in_u ∪ S^out_u ∪ P and S^in_v ∪ S^out_v ∪ P are acyclic. For u≠v this implication is false: the digraph in [S3] contains S^out_u and S^in_v but omits S^in_u and S^out_v. A path P with start(P)∈S^out_u and end(P)∈R_u can satisfy [S1]–[S3] while P together with the path end(P)→root in S^in_u and root→start(P) in S^out_u forms a directed cycle, making P simultaneously switching and bad. Thus the assertion that every ear path is exactly one of the three types is not established. This is load-bearing because later arguments, such as the case split in the proof of Lemma 6.4 and the classification of ear paths in Case 5 of Theorem 1.2, read Lemma 4.2 as an exclusive dichotomy. The authors should either provide a correct proof of exclusivity or weaken the lemma to an inclusive classification and re-verify all later uses of the dichotomy.","section":"§4.1, Lemma 4.2"},{"comment":"The proof that the four augmentations preserve strong 2-connectivity is too compressed in the collarette case. The sentence 'Observe that, since D is strongly 2-connected and |V(D)|≥4, we can guarantee that the vertices in W have the required property' is not a proof: one needs a case analysis showing that each vertex in W, including the internal vertices of the added chain, has two vertex-disjoint paths to and from V(D*)\\W. The subsequent claim that failure of this property forces u and v to have the same unique out-neighbour is not obvious and is not justified. Since Theorem 1.4 is needed to ensure that every intermediate digraph in the sequence of Theorem 1.2 is strongly 2-connected, this argument should be expanded.","section":"§3.3, Theorem 1.4"}],"minor_comments":[{"comment":"The displayed list of possible edges contains '(e(u),b(v))' twice and should list the four distinct edges {(b(u),b(v)), (b(u),e(v)), (e(u),b(v)), (e(u),e(v))}.","section":"§3.3, proof of Theorem 1.4, chain case"},{"comment":"The inference 'by (4), neither O nor I is non-parallel switching. Thus ... end(O)∉V(Sin_w)...' should be expanded: it relies on the fact that H′ is a subdivision of H in this case, so an internal vertex of Q has exactly one outgoing and one incoming edge in H′, and therefore an ear path starting there and ending in Sin_w for w≠u would indeed be non-parallel switching rather than parallel switching. This point is currently implicit.","section":"§7, Case 5, Claim 1"},{"comment":"The abbreviations 'exp.' and 'aug.' in the caption of Figure 6 are not defined in the caption; please spell them out or refer to the surrounding text.","section":"§3.4, Figure 6"}],"recommendation":"major_revision","confidential_remarks":"The main theorem, if correct, is likely to be of considerable interest to the digraph minors community. The self-citation to [Wie20] is not a concern: that theorem is published and is the natural external ingredient for deriving Theorem 1.1 from Theorem 1.2. The primary issue is the unsupported exclusivity claim in Lemma 4.2; if the authors can fix that proof or reformulate the lemma as an inclusive classification and adjust the dependent arguments, the paper should be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper proves a directed analogue of Seymour's splitter theorem for strongly 2-connected digraphs under butterfly-minors, with a sequence built from four augmentations. That is genuinely new and is the kind of structural result that should anchor future work on digraph connectivity and minors. The proof is long but organized: the ear-path trichotomy (augmenting, bad, switching) is a real organizing idea, and the four augmentation types (basic, chain, collarette, bracelet) are forced by examples like the anti-chain discussion. The paper is also honest about McCuaig's unpublished claim and does not hide the reliance on Wiederrecht's base-minor theorem. I checked the main soft spot flagged in the stress-test. Lemma 4.2's 'Thus Sin_u ∪ Sout_u ∪ P ... are acyclic' is indeed too fast. But the conclusion is still right: a switching path with respect to (u,v) has endpoints in Sout_u ∪ Sin_v; if it were bad at u, both endpoints would have to lie in Sout_u, and the return path required for a cycle would also be in Sout_u, hence in [S3]'s acyclic set. The same works for v, and for other branchsets the endpoint sets are disjoint. So the trichotomy holds, but the write-up should spell this out rather than hand-wave with 'Thus.' That is a minor presentation issue, not a load-bearing flaw. The other soft spot is Theorem 1.4: the proof that the four augmentations preserve strong 2-connectivity is more of a sketch, especially for chain, collarette, and bracelet. The claims about the set W and the path extensions are plausible but not fully verified in the text. This is worth tightening in revision, but it does not undermine the main theorem. The main theorem's proof is inductive and depends on the lemmas in Sections 5-7. I did not find circularity; the use of [Wie20] is a coauthor citation but the result is published and independent enough. No free parameters, no invented entities, and the description of the base B2 is clean. Bottom line: this is a paper for structural graph theorists, especially people working on directed minors and connectivity. It deserves a serious referee. With the terse spots cleaned up, it should be accepted. Recommendation: send to peer review, and in the report ask for a fuller justification of the Lemma 4.2 disjointness and a more detailed proof of Theorem 1.4.","headline":"A serious and likely correct directed splitter theorem; the written proof has a few terse spots, but the stress-test concern about Lemma 4.2 does not hold up.","tokens_in":677,"tokens_out":1050,"would_cite":true,"duration_ms":82435,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C40","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes a directed splitter theorem: if $H$ is a butterfly-minor of $D$ and both are strongly 2-connected, then $D$ can be built from $H$ by a sequence of strong-2-connectivity-preserving augmentations of four fixed types.","keywords":["strongly 2-connected digraphs","butterfly-minor","generation theorem","splitter theorem","braces","ear paths","augmentations"],"falsifier":"Lemma 4.2 claims that for every $H$-expansion $H'$ in a strongly 2-connected digraph $D$, every $H'$-ear path is exactly one of augmenting, switching, or bad. To test this, enumerate all ear paths in a small pair, for example $H$ equal to the bidirected triangle and $D$ a strongly 2-connected digraph on four or five vertices containing it as a butterfly-minor, and check each path against the augmenting conditions, the switching conditions, and the bad-path cycle condition. A single path that satisfies none of the three classes, or satisfies two, falsifies the trichotomy and with it the inductive step on which Theorem 1.2 rests.","tokens_in":37561,"feed_emoji":"🔄","tokens_out":12616,"duration_ms":104507,"temperature":0.7,"pith_summary":"This paper proves a generation theorem for strongly 2-connected digraphs. Starting from the single digraph $A_4$ and all bidirected cycles $C_k$ with $k\\geq 3$, every strongly 2-connected digraph can be built by repeatedly applying four local operations: basic, chain, collarette, and bracelet augmentations. The stronger, more general statement is a splitter theorem: whenever $H$ is a butterfly-minor of $D$ and both are strongly 2-connected, there is a sequence $D_0=H,\\dots,D_n=D$ in which every intermediate digraph is strongly 2-connected and each step is one augmentation. A sympathetic reader should care because this is the directed analogue of ear decompositions for 2-connected graphs and of splitter theorems for 3-connected graphs, adapted to the butterfly-minor relation. The cost of the result is that one operation, the chain augmentation, can introduce arbitrarily many vertices in a single step; the paper argues this is unavoidable because the butterfly-minor order has infinite anti-chains built from bidirected paths.","feed_headline":"Four local moves generate every strongly 2-connected digraph","feed_subtitle":"From A4 plus all bidirected cycles, every such digraph is reachable step by step, staying strongly 2-connected throughout.","key_machinery":"The argument is carried by ear paths inside an $H$-expansion, the subgraph of $D$ that models $H$ via a butterfly-model. An $H'$-ear path is a directed path that meets the expansion only at its endpoints, or a single missing edge between vertices of the expansion. The proof's engine is a trichotomy (Lemma 4.2): every such ear path is exactly augmenting, switching, or bad. Augmenting paths immediately yield a basic augmentation; switching paths run parallel to the model of an edge of $H$ and let the expansion be re-optimised by switching onto the path to obtain a new expansion; bad paths form a directed cycle with the in- and out-star of one modelled vertex and are handled by the concepts of blocking vertices and escapes, which force the existence of a path that can produce a chain or collarette augmentation. Laced paths, in which two paths intersect in a sequence of directed segments, supply the normal form that converts these configurations into the four concrete operations.","core_discovery":"At the core is Theorem 1.2. Let $D$ and $H$ be strongly 2-connected digraphs with $H$ a butterfly-minor of $D$, meaning $H$ can be obtained from $D$ by deleting vertices and edges and contracting only edges that are the unique outgoing edge of their tail or the unique incoming edge of their head. The theorem asserts a sequence $D_0=H, D_1,\\dots,D_n=D$ of strongly 2-connected digraphs in which each $D_i$ is obtained from $D_{i-1}$ by exactly one of four augmentations: adding an edge (possibly after splitting a vertex), weaving a directed path through an existing edge, subdividing the two edges of a digon and adding a path between the subdivision vertices, or piercing a two-edge path through a vertex of in- and out-degree two. Since the four augmentations preserve strong 2-connectivity, the sequence never leaves the class. Combined with the earlier fact that every strongly 2-connected digraph contains $A_4$ or a bidirected cycle as a butterfly-minor, this yields Theorem 1.1: the class generated from the base set $B_2$ consisting of $A_4$ and all bidirected cycles $C_k$ for $k\\ge 3$ by the four augmentations is exactly the class of strongly 2-connected digraphs.","pith_inferences":["Beyond the paper: the proof is constructive enough to suggest an explicit algorithm that, given $D$ and $H$, outputs the augmentation sequence; the paper does not analyse running time, but the case analysis indicates that the switching and escape searches are the steps to make efficient.","Beyond the paper: the same ear-path trichotomy might transfer to other directed minor relations, such as directed topological minors or higher strong connectivity, once the appropriate analogue of a bad path is identified, yielding splitter theorems for those settings.","Beyond the paper: the paper's diagnosis that bidirected paths are the only obstruction to well-quasi-ordering suggests a testable stronger claim: every butterfly-minor-closed class of strongly 2-connected digraphs that forbids arbitrarily long bidirected paths should be well-quasi-ordered.","Beyond the paper: because the chain augmentation is the only operation that adds unboundedly many vertices, a natural test extension is to ask which subclasses of strongly 2-connected digraphs can be generated using only basic, collarette, and bracelet augmentations."],"forward_implications":["Every strongly 2-connected digraph can be synthesised from $A_4$ or a bidirected cycle by finitely many applications of the four augmentations (Theorem 1.1).","The intermediate graphs in such a generation or reduction sequence can be kept strongly 2-connected at every step, so no construction ever passes through a digraph that is only weakly connected or 1-connected (Theorem 1.4).","Because the chain augmentation can add arbitrarily many vertices at once, the four operations cover the classical ear-decomposition of 2-connected undirected graphs: an undirected ear is emulated by a chain followed by a basic augmentation.","The base family must be infinite, containing all bidirected cycles, which reflects that the butterfly-minor order has infinite anti-chains; the unbounded chain augmentation is exactly the mechanism that navigates between members of such anti-chains.","Theorem 1.2 gives, in principle, a reduction mechanism: any strongly 2-connected butterfly-minor $H$ of $D$ can be enlarged back to $D$ one strong-2-connectivity-preserving augmentation at a time."],"supporting_citations":[{"why":"Supplies Lemma 2.1, the butterfly-model characterisation of butterfly-minors, on which the entire expansion-based proof rests.","marker":"[AKKW16]"},{"why":"Supplies the brace-generation ideas that the paper adapts, and is the source of the claim of a related generation result for strongly 2-connected digraphs.","marker":"[McC01]"},{"why":"Supplies the ear-decomposition theorem that the four augmentations must recover as the undirected special case.","marker":"[Whi32]"},{"why":"Supplies the splitter-theorem template: a sequence of single-step extensions between a minor and its supergraph while preserving connectivity.","marker":"[Sey80]"},{"why":"Supplies the base-set theorem: every strongly 2-connected digraph contains a member of the base set as a butterfly-minor, which turns Theorem 1.2 into the generative Theorem 1.1.","marker":"[Wie20]"}],"fun_headline_variants":["Four operations generate every strongly 2-connected digraph","All strongly 2-connected digraphs from four moves","Four local moves build any strongly 2-connected digraph","From A4 and cycles, four steps to all 2-connected digraphs","Every strongly 2-connected digraph via four simple operations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Lemma 4.2's classification: every ear path attached to a fixed $H$-expansion is exactly one of augmenting, switching, or bad; if some ear path escapes all three classes or fits more than one, the case analysis that turns ear paths into the four augmentations may miss a configuration and the induction step can fail.","fun_headline_variants_meta":{"raw":{"variants":["Four operations generate every strongly 2-connected digraph","All strongly 2-connected digraphs from four moves","Four local moves build any strongly 2-connected digraph","From A4 and cycles, four steps to all 2-connected digraphs","Every strongly 2-connected digraph via four simple operations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000227,"raw_usage":{"total_tokens":1480,"prompt_tokens":964,"completion_tokens":516,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":431}},"tokens_in":580,"tokens_out":516,"duration_ms":4876,"temperature":1.0,"reasoning_tokens":431,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:18:05.628750+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Lemma 4.2 claims that for every $H$-expansion $H'$ in a strongly 2-connected digraph $D$, every $H'$-ear path is exactly one of augmenting, switching, or bad. To test this, enumerate all ear paths in a small pair, for example $H$ equal to the bidirected triangle and $D$ a strongly 2-connected digraph on four or five vertices containing it as a butterfly-minor, and check each path against the augmenting conditions, the switching conditions, and the bad-path cycle condition. A single path that satisfies none of the three classes, or satisfies two, falsifies the trichotomy and with it the inductive step on which Theorem 1.2 rests.","supporting_citations":[],"review_version":1}